The problem: one room, no overlaps
Picture a single lecture room and a stack of requests to use it. Each request is an interval with a start time and a finish time — say [9, 10], [9:30, 11], [10, 11:30], and so on. Two requests conflict if their intervals overlap. You may accept any set of requests as long as no two of the accepted ones overlap, and your goal is to accept as many as possible. That is interval scheduling, and it is a textbook optimization problem: among all the valid (conflict-free) choices, we want the one of maximum size.
Notice what we are counting. We want the most requests, not the most hours of room usage — every accepted interval counts as one, whether it lasts ten minutes or three hours. That distinction matters, because it quietly rules out the most tempting heuristic of all. The brute-force rung would solve this by enumerating every subset of requests and keeping the largest conflict-free one, but with n requests there are 2^n subsets — hopelessly slow. Greedy promises something far better: sort once, sweep through, and decide each request on the spot.
Which greedy rule? Three that fail, one that works
Greedy means we fix an order, walk the requests in that order, and accept each one if it does not conflict with what we have already accepted. The only real decision is the rule that sets the order. Several rules sound reasonable. Earliest start time — grab whoever asks first? That fails: one request that starts at 9:00 but runs until 18:00 hogs the whole day and blocks dozens of short ones. Shortest interval — take the briefest requests, to pack in more? That fails too: a single 30-minute request wedged between two longer ones can knock out both, when keeping the two would have been better.
Fewest conflicts — pick the request that overlaps the fewest others, hoping to leave the most room? It is the cleverest-sounding of the bunch, and it still fails on carefully built examples. The rule that actually works is almost embarrassingly simple: earliest finish time first. Sort all requests by their finish time, then sweep left to right, accepting a request whenever it starts no earlier than the finish of the last one you accepted. The intuition is honest and worth holding onto: *the request that frees up the room soonest leaves the most time for everything that follows.* Among all the requests you could take first, the one ending earliest is the most generous to the future.
A tiny trace
Run earliest-finish-time on five requests. Sorting by finish time gives this order; we sweep once, keeping a running "last finish" and accepting any request that starts at or after it.
requests sorted by finish: A[1,4] B[3,5] C[0,6] D[5,7] E[6,8]
last_finish = -inf
A: starts 1 >= -inf -> ACCEPT, last_finish = 4
B: starts 3 < 4 -> skip (overlaps A)
C: starts 0 < 4 -> skip (overlaps A)
D: starts 5 >= 4 -> ACCEPT, last_finish = 7
E: starts 6 < 7 -> skip (overlaps D)
chosen = { A, D } size 2 (optimal here)Two things to take from the trace. First, the work is just a sort followed by a single linear pass, so the whole algorithm runs in O(n log n) — the sort dominates, and that is linearithmic time, a giant leap down from 2^n. Second, notice that C[0,6], the longest request, was discarded early: greedy never even considers it seriously, because A finishes sooner and clears the way for D. The length of a request is irrelevant; only its finish time steers the decision.
Why it is optimal: greedy stays ahead
A trace shows the rule winning on one example; it does not show it always wins. For that we need a proof, and the proof technique here has a memorable name: greedy stays ahead. The idea is to compare greedy's run, request by request, against any optimal solution, and show that greedy is never behind. Let greedy pick g1, g2, g3, ... (in the order it accepts them) and let some optimal solution pick o1, o2, o3, ... — both lists sorted by finish time. We will prove a single clean invariant: for every k, greedy's k-th accepted request finishes no later than the optimal's k-th, i.e. finish(g_k) <= finish(o_k).
- Base case (k = 1): greedy's very first pick is, by its rule, the request with the earliest finish time of all. So nothing can finish before g1 — in particular finish(g1) <= finish(o1). Greedy starts (at least) tied.
- Inductive step: assume finish(g_k) <= finish(o_k). The optimal's next request o_{k+1} starts after o_k finishes, hence after g_k finishes too (by the assumption). So o_{k+1} was a legal candidate for greedy when it chose g_{k+1} — it does not conflict with anything greedy has accepted.
- Greedy, among all legal candidates at that moment, picks the one finishing earliest. Since o_{k+1} was legal, greedy's choice finishes no later than it: finish(g_{k+1}) <= finish(o_{k+1}). The invariant carries from k to k+1.
- Finish the argument by contradiction: suppose optimal accepted more requests than greedy, so it has an o_{m+1} where greedy stopped at g_m. By the invariant finish(g_m) <= finish(o_m), and o_{m+1} starts after o_m, so o_{m+1} was still legal for greedy — greedy would have taken it and not stopped. Contradiction. So greedy accepts at least as many as optimal, hence exactly as many: it is optimal.
Look at the shape of that argument: it is exactly a loop invariant proved by induction, the same machinery you met in the correctness rung — only now the invariant says "greedy is ahead" rather than "the array is partly sorted". This is also our first concrete sighting of the greedy-choice property: the claim that taking the locally best step (earliest finish) never forecloses a globally optimal solution. The proof is precisely what earns that claim; without it, the property is just a hope.
A cousin problem, and an honest boundary
Change the question slightly and a new greedy appears. Suppose we must schedule all the requests, but we may open more rooms; we want the fewest rooms so that no room ever double-books. That is interval partitioning. Here the right rule sorts by start time and, sweeping through, assigns each request to any free room, opening a new one only when none is free. The number of rooms it opens equals the maximum number of intervals overlapping at any single instant — a quantity called the depth — and you clearly cannot do better than the depth, since that many requests genuinely coincide. Same domain of intervals, different objective, different greedy, but the same flavour of proof: show greedy's count matches an unbeatable lower bound.
Two final caveats keep us honest. The O(n log n) cost is asymptotic: for a handful of requests the sort's overhead is real and a dumb method might tie it, but as n grows greedy pulls hopelessly far ahead of 2^n enumeration. And remember that the elegance of the "stays ahead" proof rides entirely on the unweighted objective; it is a template for one shape of greedy argument, not a universal key. The companion technique — the exchange argument — handles many cases that "stays ahead" cannot, and the next guide is devoted to it.