Interval Problems
Interval problems are everywhere: calendar apps, scheduling, resource allocation. The secret sauce? Sort by start (or end) time, then sweep through.
The Core Pattern
Almost every interval problem starts with sorting. Then you walk through and make decisions based on overlaps.
The Key Insight
Two intervals [a, b] and [c, d] overlap if a < d and c < b. Or simpler: they DON'T overlap if one ends before the other starts.
Classic: Merge Intervals
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if merged and merged[-1][1] >= interval[0]:
# Overlaps with previous - extend it
merged[-1][1] = max(merged[-1][1], interval[1])
else:
merged.append(interval)
return mergedClassic: Meeting Rooms II
Minimum number of meeting rooms needed:
def minMeetingRooms(intervals):
starts = sorted([i[0] for i in intervals])
ends = sorted([i[1] for i in intervals])
rooms = 0
end_ptr = 0
for start in starts:
if start < ends[end_ptr]:
rooms += 1 # Need new room
else:
end_ptr += 1 # Reuse a room
return roomsCommon Interval Patterns
- Merge overlapping - Sort by start, extend end
- Insert interval - Find where to insert, then merge
- Meeting rooms - Count max concurrent events
- Non-overlapping count - Greedy by end time
Pro Tip
Drawing intervals on a timeline makes the problem much clearer. Seriously, grab a pen.