The problem
Given a messy list of intervals, collapse every group that overlaps into a single span. Bookings 1 to 3, 2 to 6, and 8 to 10 become 1 to 6 and 8 to 10.
The sort first trick
The whole task becomes easy once intervals are sorted by start. After sorting, any interval that overlaps a previous one must overlap the most recently emitted span, so you never look further back than one step.
The sweep
- Sort all intervals by their start value.
- Keep a current interval, initially the first one.
- For each next interval, if its start is at or before the current end, extend the current end to the larger of the two ends.
- Otherwise the current span is finished. Emit it and make the next interval the new current.
Why one pointer is enough
Because the list is sorted, a later interval can only reach back to the current merged span. If it does not touch that span, it cannot touch any earlier one either. That is what lets a single linear pass finish the job after the sort.
Key idea
Sort by start, then merge each interval into the running span when it touches, otherwise close the span and open a fresh one.