Merge Intervals
Sort by start time, sweep once. Overlap → extend. No overlap → push new. One sort, one pass — every interval problem solved.
Check every pair for overlap — O(n²). Sort once, sweep once — O(n log n)
The insight: sorting by start time means you only ever compare with the last merged interval. After sorting, any overlapping interval must start at or before the current interval's end — you never need to look further back. One sort, one pass.
Interval Problem Types
Three variants — each needs a slightly different approach.
Sort by start. Sweep. Extend or push.
3 phases: before / overlap / after.
Min-heap of end times counts active slots.
The 3-Step Framework
The overlap condition and merge logic — memorize these cold.
Always sort intervals by start time first (unless input guarantees sorted order). This makes overlap detection a single backward comparison.
intervals.sort(key=lambda x: x[0]) merged = [intervals[0]]
Two intervals [a,b] and [c,d] overlap if c ≤ b. Merge to [a, max(b,d)]. Must use max — the new interval might be fully contained.
if start <= merged[-1][1]: # overlap
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])Minimum meeting rooms and maximum CPU load need the earliest-ending active interval — that's a min-heap of end times. Sort by start, push end times, pop when intervals finish.
import heapq
rooms = []
for start, end in sorted(intervals):
if rooms and rooms[0] <= start:
heapq.heapreplace(rooms, end)
else:
heapq.heappush(rooms, end)
return len(rooms)Recognition
Interval problems are recognizable — look for these phrases.