Interval Problems

Problems involving start-end intervals form a tight cluster solvable with greedy approaches plus sorting. Worth learning as a family.

Merge overlapping intervals

Given a list of intervals, output the non-overlapping merged set. Sort by start. Walk through; if the current interval starts at or before the last merged one's end, extend the last; otherwise append a new interval. $O(n \log n)$.

Maximum non-overlapping intervals

Given a list of intervals, pick the maximum number that don't overlap. Sort by END time, walk through; pick each interval whose start is after the previously picked interval's end. Greedy by earliest end. $O(n \log n)$.

Minimum meeting rooms

Given meeting intervals, how many rooms are needed? Two clean approaches:

1. Sort starts and ends separately. Walk both with pointers; on each start, if there's a free room (the next end is later than this start), use it; otherwise allocate a new room. 2. Sort by start time; maintain a min-heap of current end times. For each new meeting, pop ends ≤ this start (rooms freed); push the new end. The heap's max size is the answer.

Both $O(n \log n)$.

Insert interval

Insert a new interval into a sorted, non-overlapping list, merging with overlaps. Single pass — copy intervals ending before the new one, merge intervals overlapping the new one, copy the rest. $O(n)$.

The shared structure

These all decompose into: (1) sort by some criterion; (2) sweep through and maintain a small state. The sort is the only $O(n \log n)$ step; the sweep is linear. Once you see "intervals" plus "find the best/count/merge," sort first and start sweeping.