Merge Intervals
Last Updated: March 29, 2026
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 real challenge here isn't detecting overlap between two intervals. It's efficiently figuring out which intervals overlap with which when there could be thousands of them. If the intervals were sorted, this would be much easier, because overlapping intervals would be adjacent. That observation is the key to the optimal solution.
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
The most straightforward idea: for every pair of intervals, check if they overlap. If they do, merge them into one interval, and then repeat the process until no more overlaps exist.
Think of it like this. You have a pile of paper strips on a timeline. You pick up two strips, and if they overlap, you tape them together into one longer strip. Then you go back and check all remaining pairs again. You keep doing this until no two strips overlap.
This approach is correct but painfully slow. Each merge pass requires checking all pairs, and each merge reduces the count by one, so you might need many passes.
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.
This approach works but is extremely slow due to repeated pairwise comparisons on unsorted data. What if we sorted the intervals first so that overlapping intervals were always adjacent?
Approach 2: Sort and Merge
Intuition
Here's the key insight: if you sort the intervals by their start times, any intervals that overlap must be adjacent in the sorted order. Why? Because if interval A starts before interval B, the only way they can overlap is if A's end reaches into B's start. And since everything is sorted, there's no interval C between them that could "bridge" a gap.
So the algorithm becomes: sort the intervals, then walk through them one by one. Keep a "current" merged interval. If the next interval overlaps with the current one (its start is less than or equal to the current end), extend the current interval's end. If it doesn't overlap, the current interval is complete, so save it and start a new one.
One subtle point: when extending the current interval, use max(currentEnd, nextEnd), not just nextEnd. An interval like [1,10] might completely contain [2,5], so the merged end should stay at 10, not shrink to 5.
Sorting by start time creates a crucial invariant: for any two adjacent intervals in the sorted list, the first one always starts at or before the second one. This means the only question for overlap is whether the first interval's end reaches the second interval's start.
Because we process intervals left to right and only look backward at the most recent merged interval, we never miss an overlap. Any interval that could overlap with the current merged interval must be adjacent to it in sorted order. This is a greedy approach where the sorting guarantees local decisions are globally correct.
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).