Merge Intervals
Sort by start, then sweep — merging overlapping intervals in O(n log n).
arrayssortingintervals
Intro
Given a list of intervals, merge all overlapping ones. The cleanest solution is sort by start, then iterate, extending the last interval if it overlaps.
Key insight
After sorting by start, two intervals overlap iff the second starts before the first ends.
Approach
- 1Sort intervals by start.
- 2Initialise result with the first interval.
- 3For each next interval: if it starts within the last interval, set last.end = max(last.end, next.end); else append.
Complexity
Time
O(n log n)
Space
O(n) for the output
Code
Snippetpython
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 out
Pitfalls
- Comparing `s < out[-1][1]` — depends on whether intervals are inclusive on the end.
- Sorting by end (also works) but breaks the simple invariant above.
Variants & follow-ups
- Insert Interval (LC 57)
- Non-overlapping Intervals (LC 435)