GreedyGreedy
Merge Intervals
Sort intervals by start and sweep once, extending the current interval while the next one overlaps and emitting it when a gap appears.
A
A
B
B
C
C
D
D
E
E
E
F
F
Intervals (input order)
| id | start | end | state |
|---|---|---|---|
| A | 1 | 3 | — |
| B | 3 | 5 | — |
| C | 4 | 6 | — |
| D | 9 | 11 | — |
| E | 12 | 15 | — |
| F | 8 | 10 | — |
1/106 intervals arrive in no particular order, and any that touch or overlap should come out as one. Drawn on the shared axis the answer is already visible as the connected blocks of filled columns — the algorithm's job is to find them in one pass instead of by eye.
Interval being examinedAccumulator (the run being built)Finished merged intervalAbsorbed into a merged interval
PseudocodeLearn Merge Intervals →
1sort intervals by start time2out = []3cur = the first interval4for (s, f) in the rest:5 if s <= cur.end: # overlapping, or merely touching6 cur.end = max(cur.end, f) # absorb it, extend the accumulator7 else:8 out.append(cur); cur = (s, f) # a real gap: flush and restart9out.append(cur)10return outVariables
input6
horizon15
Complexity
best O(n)
avg O(n log n)
worst O(n log n)
space O(n)
Speed