Merge Intervals
Intervals: lesson 2 of 4
Hold one block open, stretch it while they touch, close it on a gap.
Lesson 2 of 4 · 5 min
Merge Intervals
Step 1 of 8
output0
Four spans, already sorted by start: 1–3, 2–6, 8–10, 9–11.
The Idea
Sort by start, then hold exactly one block open.
If the next interval starts at or before the open block's end, they touch: stretch the end to whichever is larger. Otherwise there is a gap, so close the block and open a new one. Every interval is looked at once.
Real-World Example
A driver's tracked stops on a timesheet. Three overlapping GPS windows at the depot should read as one block of time at the depot, not three — the overlaps are noise from the sensor, and merging turns them into the fact you actually bill.
The Code
spans = [(1, 3), (2, 6), (8, 10), (9, 11)]
spans.sort() # by start — the whole trick
merged = [list(spans[0])]
for s, e in spans[1:]:
if s <= merged[-1][1]: # touches or overlaps the open block
merged[-1][1] = max(merged[-1][1], e)
else:
merged.append([s, e]) # real gap: close this one, open the next
print(merged)Your turn
Put the steps in the right order.
- Stretch the open block's end to the larger of the two ends
- Sort the intervals by start
- Open a new block whenever the next interval starts after the open end
- Put the first interval in the output as the open block
- Walk the rest, comparing each start with the open block's end
Mini quiz
1 / 3