Ranges that touch
Problems about calendars, booking systems, and number lines often hand you a set of intervals, each with a start and an end. Many of these ranges overlap or sit adjacent, and the task is to combine them, count free slots, or check conflicts. The merge intervals pattern handles all of these.
Sort then fold
The key insight is that overlaps only matter between neighbors once intervals are ordered.
- Sort the intervals by their start value.
- Keep a current merged interval and walk the rest in order.
- If the next interval starts at or before the current end, extend the current end to the larger of the two ends.
- Otherwise the gap is real, so push the current interval and start a new one.
Because a single sorted pass decides every merge, the whole routine is dominated by the sort.
Why sorting unlocks it
Without ordering, any two intervals could overlap, forcing pairwise comparison. Sorting guarantees that if the next start lies beyond the current end, no later interval can reach backward, so you never need to look behind you.
Key idea
Sort intervals by start so overlaps become a local question, then fold each interval into the previous one or emit it in a single sweep.