Merge intervals
Overlapping meetings, ranges, and calendar problems.
High interview relevanceRoadmap: Intermediate
| Time | O(n log n) |
|---|---|
| Space | O(n) |
Why it costs this much
Sorting by start time costs O(n log n), and one pass then merges neighbors in O(n).
Code
def merge(intervals):
out = []
for s, e in sorted(intervals): # O(n log n)
if out and s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e) # extend the previous interval
else:
out.append([s, e]) # one O(n) pass
return outCommon pitfalls
Forgetting to sort is the usual bug. Decide up front whether intervals that only touch (end equals next start) should merge.