Merge intervals
We'll cover the following
Given time ranges written start-end, merge all the ones that overlap.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
1-30
2-61
5-72
8-103
15-184
17-205
30-346
31-367
33-388
40-419
45-5010
47-5211
Sorted by start time for you. Now sweep left to right and keep a growing list of merged intervals.
1 / 14
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n log n) | O(n) | The sort dominates; the sweep is linear. |
In Python
def merge(intervals):
intervals.sort()
out = [intervals[0]]
for s, e in intervals[1:]:
if s <= out[-1][1]: out[-1][1] = max(out[-1][1], e)
else: out.append([s, e])
return outSummary: say it in the interview
- Sort by start. Now overlapping intervals sit next to each other. Compare each interval with the last merged one: if it starts before that one ends, stretch the end. Otherwise start a new one.
- Time O(n log n), space O(n). The sort dominates; the sweep is linear.