Merge Intervals
The Intuition
You're standing at a whiteboard scheduling meetings for a conference room. Someone hands you a pile of sticky notes, each with a start time and end time, in no particular order. Your job: figure out which meetings overlap and combine them into blocks.
First thing you do, obviously, is sort the sticky notes by start time. Now they're in chronological order on the whiteboard. You look at the first meeting. Then you look at the next one. Does it start before the current meeting ends? If yes, they overlap, so you extend the current block's end time to whichever meeting ends later. If the next meeting starts after the current one ends, there's a gap. That's a separate block.
You just walk left to right across the whiteboard, one meeting at a time. Either you merge it into the current block or you start a new block. One pass after sorting. The sort is O(n log n) and the merge pass is O(n), so the sort dominates.
Merging overlapping time slots, inserting new intervals, finding free time, meeting room scheduling, or any problem involving range overlap detection.
- Intervals are already disjoint
- Need to find gaps between intervals (different problem)
- Intervals have weights/priorities (use greedy with sorting)
Variations:
- Merge overlapping: Combine all overlapping intervals into non-overlapping set.
- Insert interval: Add a new interval and merge any resulting overlaps.
- Interval intersection: Find the intersection of two sorted interval lists.
- Sweep line: Process interval start/end as events for complex overlap counting.
- single interval
- no overlaps
- fully overlapping
- unsorted
Key Points
- •Sort intervals by start time first
- •Compare current interval's start with previous interval's end
- •Merge overlapping intervals by extending the end time
- •For insertion, find the correct position then merge surrounding overlaps
- •Sweep line variant: process start/end events separately
Code Template
1 def merge_intervals(intervals):
2 """Merge all overlapping intervals."""
3 intervals.sort(key=lambda x: x[0])
4 merged = [intervals[0]]
5
6 for start, end in intervals[1:]:
7 if start <= merged[-1][1]:
8 merged[-1][1] = max(merged[-1][1], end)
9 else:
10 merged.append([start, end])
11
12 return merged
13
14 def insert_interval(intervals, new):
15 """Insert and merge a new interval into sorted intervals."""
16 result = []
17 i = 0
18 n = len(intervals)
19
20 # Add all intervals that end before new starts
21 while i < n and intervals[i][1] < new[0]:
22 result.append(intervals[i])
23 i += 1
24
25 # Merge all overlapping intervals with new
26 while i < n and intervals[i][0] <= new[1]:
27 new[0] = min(new[0], intervals[i][0])
28 new[1] = max(new[1], intervals[i][1])
29 i += 1
30 result.append(new)
31
32 # Add remaining intervals
33 while i < n:
34 result.append(intervals[i])
35 i += 1
36
37 return result
38
39 def is_overlap(intervals):
40 """Check if any intervals overlap."""
41 intervals.sort(key=lambda x: x[0])
42 for i in range(1, len(intervals)):
43 if intervals[i][0] < intervals[i - 1][1]:
44 return True
45 return FalseCommon Mistakes
- Forgetting to sort the intervals first
- Using start of next instead of end of current for overlap check
- Not handling the edge case where one interval fully contains another