How do you prove earliest-finish-time selection is optimal for activity selection?
answer
- swap, do not enlarge
- compare the two first picks
- an earlier end keeps the rest feasible
- then recurse on what remains
- after k picks, greedy finishes no later
basics
~20 sTake any optimal schedule and swap its first activity for the greedy's first pick. The greedy's pick finishes no later, so every remaining activity still fits and the schedule stays the same size. Repeat down the list: greedy can never be smaller.
solid answer
~50 sThis is the exchange argument, and it has two halves. **Exchange:** let some optimal schedule pick activity `x` first and let the greedy pick `g`, the earliest-finishing activity of all. Since `end(g) <= end(x)`, replacing `x` with `g` leaves every later activity in that optimal schedule still compatible, so you get another optimal schedule of the same size that agrees with the greedy on the first choice. **Induction:** the remaining subproblem is the same problem over the activities starting after `end(g)`, so apply the argument again; after `k` steps the greedy agrees with an optimal schedule on all `k` first picks. The equivalent phrasing is *greedy stays ahead*: after `k` selections the greedy's `k`-th finish time is no later than the `k`-th finish time of any other feasible schedule, so it can never run out of room first, so it is never shorter.
go deeper
Know that the rule has a proof and that it works by swapping, not by testing examples. Being able to say 'the earliest-finishing pick can replace any other first pick without breaking anything' is enough at this level.
Deliver the exchange step cleanly: the greedy's first pick ends no later, so everything the other schedule kept still fits, so sizes match, then recurse. Say explicitly that the swap preserves size rather than increasing it.
Show you use the proof as a decision tool. When a variant lands, run the exchange step on it out loud and report whether feasibility and the objective both survive, rather than pattern-matching to 'intervals means sort by end'.
Be the person who insists a proposed greedy comes with its one-line argument before it ships. Untested greedy rules in scheduling code fail silently on rare inputs, and the cost of that is a correctness incident nobody can reproduce.
## What is being proved Earliest-finish-time selection is a rule, not a proof. The claim needing support is: **for maximizing the count of pairwise non-overlapping activities, the schedule produced by repeatedly taking the earliest-finishing compatible activity has the maximum possible size.** Note what is *not* claimed — not that the schedule is unique, not that it fills the most time, not that it is optimal under any other objective. Interviewers ask for this proof because a candidate who can produce it can also tell, on an unfamiliar variant, whether the greedy still applies. ## Setup and notation Activities are ranges with a start and an end. Two are compatible when their ranges do not overlap under whatever endpoint convention the problem states. A *schedule* is a set of pairwise compatible activities. Sort all `n` activities by end time ascending; the greedy walks that order and accepts an activity whenever it is compatible with the last accepted one. ## The exchange step Let `G = g1, g2, ...` be the greedy schedule and let `O` be **any** optimal schedule, its activities listed in increasing end order as `x1, x2, ...`. The greedy's first pick `g1` is the globally earliest-finishing activity, so `end(g1) <= end(x1)`. Now build `O' = (O without x1) plus g1`. Is `O'` a valid schedule? Every activity in `O` after `x1` was compatible with `x1`, meaning each starts at or after `end(x1)`. Since `end(g1) <= end(x1)`, each of them also starts at or after `end(g1)`, so each is compatible with `g1` too. Nothing else in `O` overlapped `x1`, so nothing else can overlap something ending even earlier. `O'` is valid, and `|O'| = |O|`, so `O'` is also optimal. **Conclusion of the step: there exists an optimal schedule whose first activity is the greedy's first activity.** The direction here is the part people get wrong when reciting it. The swap does not make the schedule *bigger* — it cannot, `O` was already optimal. It makes an optimal schedule *agree with the greedy* on one more position. That is the entire mechanism. ## The induction After fixing `g1`, everything compatible with `g1` forms a strictly smaller instance of the identical problem: choose the maximum number of non-overlapping activities from those starting at or after `end(g1)`. The greedy's behaviour on the original instance restricted to that region *is* the greedy on the subinstance. By induction on the number of activities, the greedy solves it optimally; combined with the exchange step, `|G| = |O|`. The base case is the empty instance, where both schedules are empty. ## The 'stays ahead' phrasing An equivalent and often faster way to say it: prove by induction that **after `k` selections, the greedy's `k`-th finish time is no later than the `k`-th finish time of any feasible schedule.** Then suppose some schedule had `m > |G|` activities. Its first `|G|` activities finish no earlier than the greedy's, so its `(|G|+1)`-th activity starts after the greedy's last finish and would have been compatible — meaning the greedy would have accepted it or something ending even earlier, contradicting the greedy having stopped. Either phrasing is acceptable; pick one and finish it, rather than gesturing at both. ## Where the argument breaks, and why that matters The exchange step used exactly one property: swapping in an earlier-finishing activity preserves feasibility *and size*. Change the objective so each activity carries a value and you are maximizing total value, and the swap no longer preserves the quantity being optimized — `g1` may be worth far less than `x1`. The proof collapses, and so does the rule; the weighted variant genuinely needs a different technique. Similarly, if activities can be interrupted and resumed, or if there are several parallel tracks, the subproblem after the first pick is no longer the same problem, and the induction has no footing. This is why the proof is worth memorizing as a *shape* rather than as words. In an interview you will meet a disguised variant, and the honest way to decide whether the greedy survives is to try the exchange step on it and watch whether feasibility and objective both survive the swap. If they do, you have both an algorithm and its correctness in the same breath. If they do not, you have just discovered — cheaply, before writing anything — that you need a different method. ## A word on uniqueness The proof shows the greedy attains the maximum size; it says nothing about which maximum-size set you get. Ties in end time, or genuinely different optimal sets of equal size, are common. If an interviewer asks "is this the answer or an answer," the correct reply is that the size is unique and the set generally is not.
- Does the exchange argument show the greedy finds the unique optimal schedule?No. It shows the greedy's schedule has maximum size. Several different sets can share that size — ties in end time alone produce them — so the count is unique while the chosen set generally is not. Saying this unprompted avoids a common overclaim, and it also explains why two correct submissions can print different activity lists.
- Which part of the argument fails once each activity carries a value to maximize?The swap. Replacing the optimal schedule's first activity with the earliest-finishing one preserves feasibility but not total value, since the earlier-finishing activity may be worth much less. Feasibility survives and the objective does not, so the exchange step proves nothing and the greedy is genuinely wrong for that variant — it needs a different technique entirely.
- How would you sanity-check the proof on a variant before trusting the greedy?Run the exchange step mentally: swap the optimal solution's first choice for the greedy's and ask whether the result is still feasible and still just as good. Both must survive. If parallel tracks or interruptions make the leftover instance a different problem, the induction also fails, and that is your signal to stop and reach for another method.
saying these in an interview costs you the question
- Says the swap makes the schedule larger
- Proves it works on one example and stops
- Claims the greedy yields the unique optimal set
- Cannot state what the induction recurses on
- Asserts the same proof covers weighted activities