Lesson 15.2 · Intervals
Sort by Start, Then Merge
After sorting by start, overlapping intervals are neighbours, so one pass merges them.
12 min
Think of it like this
Combining a day's calendar bookings: list them by start time, and any booking that starts before the previous block ends gets absorbed into that block.
1.The merge pass
Sort by start. Keep the last merged interval. For each next interval, if it starts at or before the last one's end, extend the end to the larger of the two ends; otherwise start a new block.
Remember to take the max of the ends: a long interval can contain shorter ones that come after it.
[[1,3], [2,6], [8,10], [15,18]] (already sorted)1-3
02-6
18-10
215-18
3merged(list)
[1,3]
Step 1/4Start with [1,3].
Remember
- Sort by start: overlaps become adjacent.
- Extend with max(end, newEnd).
- O(n log n) for the sort, O(n) for the pass.
Common mistakes
- Setting the end to the new interval's end instead of the max.