Intervals

Intermediate · 16 min read · Problem-Solving Patterns, Arrays & Strings

Sort by start, then merge, insert or sweep — meeting rooms and overlaps.

Calendars, bookings, CPU jobs, flight times — interval problems are everywhere, and they share one move that unlocks almost all of them: sort first. Unsorted intervals can overlap anything, anywhere; sorted by start, an interval can only overlap the one just before it. After that, most problems are one linear pass.

Overlap, precisely

Two intervals [a, b] and [c, d] overlap when each starts before the other ends:

Merge: sort by start, then one pass

Step through it on a timeline. First the rows slide into order by start. Then each interval is compared with the end of the last merged interval (the dashed line): start ≤ end means overlap, so extend; otherwise there's a gap, so start a new merged interval.

Worked problems

Three phases, no sort needed (the list is already sorted): copy everything that ends before the new one starts, absorb everything that overlaps, copy the rest.

Which sort key?

Practice ladder

Interview questions

Why do you sort by end time when maximising the number of non-overlapping intervals?
How do you compute the minimum number of meeting rooms?

Key takeaways

Sort first. By start to merge/insert; by end to keep the most / remove the fewest; starts and ends separately for peak overlap.
Overlap: each starts before the other ends. Decide whether touching counts.
Merging extends with max; inserting uses three phases on an already-sorted list.
The sweep line (+1 at starts, −1 at ends) answers "how many at the busiest moment".

Previous: Prefix Sums & Difference Arrays · Next: Binary Search