The standard proof that a greedy rule is optimal starts from some optimal solution and rewrites it, choice by choice, into the rule's answer, checking after every swap that what remains is still legal and still as large. The lab performs that rewriting rather than describing it. On the earliest-finish rule every swap survives; on shortest-first it fails at the first swap, and the failure is in the feasibility half rather than the size half.
Core ideas
Three ideas: what the argument is for, what has to be rechecked after each swap, and why a rewriting that never breaks is a proof while a rewriting that happens to succeed on one instance is not.
An exchange argument never asks what the optimum is. It says: take any optimal solution O whatever it is, and show that O can be edited into greedy's answer without ever losing optimality. If that editing always works then greedy's answer is itself optimal, because it is what O became. The edit is done in greedy's order: the first swap forces greedy's first choice in, the second forces its second choice in, and so on.
Putting gᵢ into the set is only safe if the result is still a legal selection — no two intervals overlap — and still has as many intervals as before. Those are different failures and the panel reports them in different columns. On the shortest-first trap the set after the first swap is still size 2 and is not feasible; on the fewest-conflicts trap the set after the second swap is still feasible and has lost an interval. A proof has to close both.
The panel starts from one optimum — the one its enumeration happened to return — and edits that one. The theorem quantifies over all optimal solutions and all instances. So a green chain here does not prove the rule, and a red one does refute it: a single optimum that cannot be rewritten is a counterexample to the argument, and on these instances it comes with the losing rule's own trap attached.
The material
What an exchange argument claims, the two checks each swap must pass, the swap that breaks on a wrong rule, and the case where the argument has nothing to do.
Let g₁, g₂, …, g_k be greedy's choices in the order it made them, and let O be any optimal solution. For i = 1, 2, …, k in turn, replace the i-th element of O (in the same order greedy uses) by gᵢ, leaving gᵢ alone if it is already there. The argument succeeds when every intermediate set is feasible and has the same size as O.
If it succeeds then after k swaps the set contains all of greedy's choices and is still optimal, and a feasible set containing greedy's answer cannot be larger than greedy's answer, because greedy stopped only when nothing more could be added. So greedy's answer is optimal. That last step is worth saying out loud: it is where the rule's own stopping condition enters the proof, and it is why the argument is about greedy rather than about swaps.
The lab opens on 0-5, 4-6, 5-10, labelled A, B, C. The optimum is A C, size 2, out of eight subsets. Under earliest finish, greedy also selects A C, so both swaps find their target already in place and the chain survives. Under shortest first, greedy selects B alone; the first swap puts B in for A, giving the set B C, which is still size 2 and is not feasible, because B runs from 4 to 6 and C from 5 to 10. The chain stops there.
That is the whole of the negative result and it took one swap. The proof template for earliest finish does not merely fail to apply to shortest first; it produces, at a named step, a specific infeasible set from a specific optimum. The panel prints the set — B C — and runs a feasibility check on it separately, so the verdict is not the chain's own opinion of itself.
On 0-10, 1-2, 3-4, 5-6, 7-8 under earliest start, greedy takes A alone. The first swap puts A in for B and gives A C D E, which has the right size and overlaps, since A spans the whole day. On 0-2, 2-4, 4-6, 6-8, 1-3, 3-5, 5-7 under fewest conflicts the opposite happens: the first swap is a no-op, the second puts D in for B, and the resulting set A D C is perfectly feasible and has three intervals where the optimum had four. On the eleven-interval instance under earliest start the chain manages both — three swaps, the first two same-size and overlapping, the third feasible and down to three.
So the size column and the feasibility column both fire somewhere, on different instances, and a reader who only watched one of the traps would conclude the argument always breaks the same way. It does not, and there is no reason it should: the two obligations are independent.
For interval scheduling with the earliest-finish rule, every swap in the sequence above keeps the set feasible and keeps its size, for every instance and every optimal solution. Hence the rule is optimal on every instance.
Take the first index i at which O and greedy differ, so greedy's first i - 1 choices are already in O. Let o be the i-th interval of O in increasing finish order and gᵢ greedy's i-th choice.
Greedy considered every interval compatible with its first i - 1 choices and took the one finishing earliest, so f(gᵢ) ≤ f(o). Replacing o by gᵢ therefore leaves every later interval of O still compatible, because each of them starts at or after f(o) and so at or after f(gᵢ). The earlier intervals of O are greedy's own first i - 1 choices, which gᵢ is compatible with by construction.
The size is unchanged because one interval was removed and one added, and gᵢ was not already present by the choice of i. Repeating drives the first difference forward one position at a time, so after at most k swaps O contains all of greedy's choices while remaining feasible and optimal.
□
The step that breaks for the other three rules is the inequality f(gᵢ) ≤ f(o). Nothing about sorting by length, or by start time, or by conflict count makes greedy's i-th choice finish no later than the optimum's, and the traps are instances where it finishes later. That single inequality is the entire content of the proof, and it is the reason earliest finish is the rule and the other three are folklore.
On the eleven-interval instance under earliest finish, the panel reports four swaps and every one of them reads “already there”. Nothing was exchanged. That is not the argument working particularly well; it is the enumeration having returned A D H K, which is greedy's own answer, so the first difference never arrives. Switch the rule to shortest first on the same eleven and the first swap becomes real: A out, B in, giving B D H K, still feasible and still four.
This is a small trap in reading the lab and a large one in reading a proof. A chain of no-ops proves nothing about the rule, because the argument was never exercised. When you want to see the machinery work, pick a rule whose answer differs from the optimum the panel found, and watch a swap actually replace something.
Measured on this page: on the three-interval instance the earliest-finish chain survives 2 swaps and the shortest-first chain breaks at swap 1 with the set B C. Proved on this page: the earliest-finish chain survives every swap on every instance, by the inequality above. The lab cannot reach the second sentence, and the second sentence is the only one that licenses using the rule on an input nobody has tried.
Interactive
Four rules on one instance, each beside the best of every subset
Method
Four steps, and the third is the one that is usually skipped.
The argument is indexed by greedy's own sequence, not by the optimum's. Get g₁, g₂, … on paper before touching O, because the swap at position i is defined by gᵢ and nothing else.
Earlier positions are already equal by construction and swapping there is a no-op. If every position is a no-op, as happens on the eleven-interval instance under earliest finish, the argument has not been exercised and you have learned nothing from it.
These fail on different instances. The shortest-first trap produces a same-size infeasible set at the first swap; the fewest-conflicts trap produces a feasible smaller one at the second. Checking only the one you expect is how a broken argument gets written up as a working one.
For earliest finish it is f(gᵢ) ≤ f(o), and the sort order supplies it directly. Write the corresponding inequality for the rule you are testing; if the rule's order does not give it to you, you have found where to look for the counterexample.
The instance is A 0-5, B 4-6, C 5-10. The optimum found by enumeration is A C, size 2, and A and C are compatible because A finishes exactly where C starts.
The two chains differ in one line and that line is the whole argument. Under earliest finish the first swap is forced by f(g₁) ≤ f(o), which here reads 5 ≤ 5. Under shortest first there is no such inequality available: g₁ is B, which finishes at 6, and the optimum's first interval finishes at 5.
It is worth being precise about what the broken chain refutes. It does not refute shortest-first on all instances by itself — the page beside it does that, by reporting greedy 1 against an optimum of 2. What it refutes is the proof: the template that works for earliest finish produces an infeasible set here, so it cannot be repaired by being more careful.
For a faded rehearsal, run the chain for earliest start on 0-10, 1-2, 3-4, 5-6, 7-8. The supplied first move is this: greedy takes A 0-10 alone, the optimum is B C D E, and the first swap puts A in for B. Say what the resulting set is, which of the two checks it fails, and what that tells you about the missing inequality — then do the same for fewest conflicts on the seven-interval instance, where the chain survives longer and fails the other check.
You should be able to state the argument without looking, explain why it ends by invoking greedy's stopping condition, produce the swap that breaks on each of the three losing rules, and say why a chain made entirely of no-ops has told you nothing.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.