loading

56. Merge Intervals — Step-by-Step Visualization

mediumLeetCode #56ArraySorting

Given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. **Example 1:** Input: `intervals = [[1,3],[2,6],[8,10],[15,18]]` Output: `[[1,6],[8,10],[15,18]]` Explanation: Since intervals `[1,3]` and `[2,6]` overlap, merge them into `[1,6]`. **Example 2:** Input: `intervals = [[1,4],[4,5]]` Output: `[[1,5]]` Explanation: Intervals `[1,4]` and `[4,5]` are considered overlapping.

Algorithm Pattern

Sorting + Greedy Merge

Key Idea

If we sort the intervals by their start times, any overlapping intervals must be adjacent in the sorted list. We can then iterate through the sorted intervals and either merge the current interval with the last interval in our result (if they overlap) or add it as a new interval.

Step-by-Step Approach

  1. Sort the intervals based on their start values.
  2. Initialize an empty `result` array.
  3. For each `interval` in sorted `intervals`:
  4. 1. If `result` is empty or `interval[0] > result[-1][1]` (no overlap): Add `interval` to `result`.
  5. 2. Otherwise (overlap): Update `result[-1][1] = max(result[-1][1], interval[1])`.
  6. Return the `result` array.

Common Gotchas

  • Don't forget to sort! The algorithm only works if intervals are processed in order of their start times.
  • Overlap happens even if `start == previousEnd`.

Related Problems

← All problems