Merge Intervals
Understanding the Problem
We're given a list of intervals, each with a start and end value, and we need to combine any intervals that overlap. Two intervals overlap when one starts before the other ends. For instance, [1,3] and [2,6] overlap because 2 is between 1 and 3. The merged result would be [1,6], taking the minimum start and maximum end.
A critical detail: intervals that share exactly one endpoint also overlap. [1,4] and [4,5] merge into [1,5] because the end of the first equals the start of the second.
The challenge is not detecting overlap between two intervals. It is efficiently figuring out which intervals overlap when there could be thousands of them. If the intervals were sorted by start time, overlapping intervals would always be adjacent, which is what the optimal solution exploits.
Key Constraints:
1 <= intervals.length <= 10^4→ With n up to 10,000, O(n^2) is 100 million operations, which is borderline. O(n log n) is comfortably within limits.0 <= start_i <= end_i <= 10^4→ Starts are always less than or equal to ends, so no need to handle invalid intervals. Values are non-negative and bounded.intervals[i].length == 2→ Every interval has exactly two elements. No degenerate inputs.
Approach 1: Brute Force (Compare All Pairs)
Intuition
For every pair of intervals, check if they overlap. If they do, combine them into one interval that spans both, then restart the search. Repeat until a full scan finds no overlapping pair.
A single merge can create new overlaps that did not exist before. Merging [1,3] with [4,6] would not, but merging [1,3] with [2,8] produces [1,8], which might now overlap with an interval that [1,3] did not reach. Restarting after each merge handles this at the cost of repeated work: each merge removes one interval, so the input can require up to n merge passes, and each pass scans all pairs.
Algorithm
- Copy the intervals into a working list.
- Use a flag
mergedto track whether any merge happened in the current pass. - For each pair of intervals
(i, j), check if they overlap (one's start is within the other's range). - If they overlap, replace interval
iwith the merged result and remove intervalj. - Set
merged = trueand restart the inner loop (since indices shifted). - Repeat until a full pass completes with no merges.
- Return the working list.
Example Walkthrough
Code
- Time Complexity: O(n^3). Each pass checks O(n^2) pairs, and we may need O(n) passes, giving O(n^3) overall.
- Space Complexity: O(n). We create a working copy of the intervals list.
The repeated pairwise comparisons on unsorted data are the bottleneck. Sorting the intervals first makes overlapping intervals adjacent, which removes the need to compare every pair.
Approach 2: Sort and Merge
Intuition
Sort the intervals by start time, and any group of overlapping intervals becomes a contiguous run in the sorted order. Once sorted, a single left-to-right scan can merge each run as it appears.
The scan keeps one current merged interval. For each next interval, its start is greater than or equal to the current interval's start because of the sort. So the two overlap exactly when the next start is less than or equal to the current end. When they overlap, extend the current end. When they do not overlap, the current interval can never overlap any later interval, since every later start is at least the current next start, which already exceeds the current end. So the current interval is finalized and the next interval becomes the new current one.
When extending, the new end is max(currentEnd, nextEnd), not nextEnd. An interval like [1,10] fully contains [2,5], so the merged end must stay at 10, not shrink to 5.
Algorithm
- Sort the intervals by start time. If two intervals have the same start, the order doesn't matter since they'll definitely overlap.
- Initialize a result list with the first interval.
- For each remaining interval:
- If it overlaps with the last interval in the result (its start <= the last interval's end), extend the last interval's end to
max(lastEnd, currentEnd). - Otherwise, add the current interval to the result as a new entry.
- Return the result list.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). The merge pass is a single O(n) scan. The sort dominates.
- Space Complexity: O(n). The result list stores up to n intervals in the worst case (when nothing merges).