Intervals
Sort intervals by a sensible key — usually start or end — and a single sweep resolves merging, overlap, and scheduling questions.
Key ideas
- —Sorting by start time lets you merge overlaps in one linear sweep.
- —Two intervals overlap when one starts before the other ends.
- —Sorting by end time is the greedy key for maximizing non-overlapping selections.
Sort first, then sweep
Almost every interval problem begins by sorting. To merge overlapping intervals, sort by start, then walk through keeping a current interval and extending its end whenever the next interval starts before that end; otherwise emit the current one and begin a new group. The sort is the O(n log n) cost; the sweep is linear.
Choosing the right key
The sort key encodes your strategy. Sorting by end time underlies the classic interval-scheduling greedy: repeatedly take the interval that finishes earliest, which provably leaves the most room for the rest. Sorting by start is better when you are merging or detecting overlap. Picking the wrong key is the most common interval bug.
Practice this
Sources
- Interval schedulingWikipedia