Intervals: Sort, Then Sweep

Interval problems hand you pairs [start, end]: meetings, bookings, ranges on a number line. Almost every one starts the same way: sort, then make one greedy pass.

The overlap test. Two intervals a and b overlap when each starts before the other ends:

a.start <= b.end and b.start <= a.end

a:  [1-----5]
b:      [3------8]      overlap
c:              [7--9]  overlaps b, not a

Once intervals are sorted by start, you only need half of it: the next interval overlaps the one you're building when nxt.start <= cur.end.

Read the problem for touching intervals like [1, 2] and [2, 3]. Closed ranges on a number line overlap (use <=). Meetings that end at 2 and start at 2 don't clash (use <).

Which key to sort by? This is the decision that matters most.

• Sort by start when you combine intervals: merging overlaps, inserting, covering a range. Sorting by start guarantees anything that could join the current group comes next.
• Sort by end when you choose intervals: the most non-overlapping ones (activity selection), fewest points to stab them all. Taking the interval that finishes first leaves the most room for the rest. Exchange argument: swap any first pick for the earliest-ending one and nothing after it can clash.

Sweep line: how many at once? "Maximum concurrent meetings", "minimum rooms", "peak passengers": turn each interval into two events, (start, +1) and (end, -1). Sort the events by time, walk them with a running counter, and track the peak.

time:   1   2   4   4   5   6
event: +1  +1  -1  +1  -1  -1
count:  1   2   1   2   1   0   -> peak 2

Ties matter. For meetings, one ending at 4 frees its room for one starting at 4, so the -1 must come first. Tuples do that for free: (4, -1) sorts before (4, 1).