greedy interval scheduling

You have one meeting room and a pile of requests, each wanting the room for a fixed start-to-end window. Some overlap; you can only host non-overlapping ones. The goal is to host as many meetings as possible. Intuition might say grab the shortest meeting, or the one that starts earliest — both are tempting and both are wrong. The correct greedy rule is: always take the meeting that FINISHES earliest among those still compatible.

The algorithm: sort all intervals by finish time; scan left to right; take the first interval, then take each next interval whose start is at or after the finish of the last one you took, skipping the rest. That is it — O(n log n) for the sort, O(n) for the scan. Why earliest-finish is right: finishing earliest frees the room as soon as possible, leaving the most time for everything else. This is proven by a 'greedy stays ahead' argument — at each rank, greedy's chosen interval finishes no later than the optimal selection's interval of that rank, so greedy can fit at least as many — or by an exchange argument replacing the optimal's first interval with the earliest-finishing one. Trace {[1,3], [2,5], [4,7], [6,8]}: sorted by finish, take [1,3], skip [2,5] (overlaps), take [4,7], skip [6,8] — two meetings, which is optimal here.

This is the canonical first example of greedy because the proof is so clean, and it is the gateway to interval partitioning (using several rooms) and to minimizing lateness. The pitfall to internalize: the obvious alternatives genuinely fail. Shortest-first can pick one tiny interval that blocks two longer compatible ones; earliest-start-first can pick one long interval that hogs the whole timeline. Only earliest-finish-first has a correctness proof.