Merge Intervals
Sort by start, then merge any interval that overlaps the last one kept.
Sweep and Merge
Problem
Given a collection of intervals, combine every pair of intervals that overlap. Return a new collection containing the resulting non-overlapping intervals in ascending order by start time. Intervals that only touch at an endpoint are considered overlapping because one starts no later than the other ends.
Examples
Input: [[5,7],[1,4],[3,6],[8,10]]
Output: [[1,7],[8,10]]
Input: [[1,2],[4,5],[2,4]]
Output: [[1,5]]
The Goal
Merge every group of overlapping intervals and return the result sorted by start. Intervals that only touch, like [1, 4] and [4, 5], count as overlapping.
For [[5, 7], [1, 4], [3, 6], [8, 10]], the first three chain together into [1, 7], and [8, 10] stays apart.
The input isn't sorted. That's the hard part: an interval near the end can overlap one near the start.
Same coverage, no overlaps
Each group of intervals that overlap becomes one interval covering the same points.
Merge when the next start is at most the last end.
Key Idea: Sort First
Sort by start. Now starts never go down, so the merged intervals come out in order, with a gap between each.
Only the last merged interval can overlap the next one. Every earlier merged interval ends before the last one starts, and the next interval starts no sooner than that. So each interval needs one comparison, with merged[-1].
Starts never go down, so nothing later reaches back past the last merged interval.
[1, 4], [3, 6], [5, 7], [8, 10]
The Algorithm
def merge(intervals):
intervals = sorted(intervals, key=lambda iv: iv[0])
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged<= merges intervals that touch. max keeps the larger end, since an interval can sit inside the last one. Checking merged first handles an empty input and starts the list with the first interval.
| Approach | Order | Time | Why |
|---|---|---|---|
| Sort, then sweep | Sort by start once | O(n log n) | One comparison per interval |
| Compare every pair | None | O(n^2) or more | Each merge can create new overlaps to check |
Walkthrough
Run it on [[5, 7], [1, 4], [3, 6], [8, 10]].
Sorting puts [1, 4] first, and merged starts with it. [3, 6] starts at 3, before 4, so the last interval stretches to [1, 6]. [5, 7] stretches it again, to [1, 7]. [8, 10] starts after 7, so there's a gap and it's appended.
The answer is [[1, 7], [8, 10]].
Checkpoint · predict the next step
Step 6 of 14 on the stage: 3 ≤ 4, where the last merged interval ends: they overlap.
merged = [1, 4] · last end 4
Pitfalls
- Sort first. Unsorted, an interval late in the input can overlap one merged much earlier, and the sweep never looks back.
- Use
start <= merged[-1][1], so touching intervals like[1, 4]and[4, 5]merge into[1, 5]. - Take the
maxof the two ends.[2, 3]sits inside[1, 10]and mustn't shrink it. - An empty input returns
[]. Theif mergedcheck covers it.
What should the algorithm return for [[1, 2], [2, 5]]?
Complexity
Sorting takes O(n log n). The sweep does constant work per interval, O(n), so the sort sets the total: O(n log n).
merged can hold every interval when none overlap, so the output takes O(n) space. The sorted copy takes O(n) more.
Sorting dominates
- Sort by startThe biggest cost.dominantO(n log n)
- Sweep and compareOne comparison per interval.O(n)
- mergedOne entry per interval when nothing overlaps.O(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n log n) | 33 | 664 | 10K | 132.9K |
| O(n) | 10 | 100 | 1K | 10K |
Sort once, then one pass does the merging.
In short
Sort intervals by start time. Walk through them, and if the current interval starts before the previous merged one ends, extend that merged interval's end; otherwise push a new interval. One sort plus one sweep.
Common mistake
Forgetting to sort first — merging only works once intervals are ordered by start.