Lesson · Greedy Algorithms and Matroids · Rules and their proofs

Greedy Rules and the Optimum

A greedy algorithm commits to a choice and never revisits it. Four rules for choosing non-overlapping activities all sound reasonable and three of them are wrong. Nothing on the page separates them except an optimum computed by trying every subset — and on the opening instance three of the four reach it. Each of the three that can fail has its own instance in the lab on which it does, and the only difference between the two runs is the input.

Open the interactive lesson Practice

greedy: take the next feasible item by some rule, and never undo a choice feasible: no two chosen intervals overlap — checked pairwise, never inferred optimum: the largest feasible subset, over all 2ⁿ subsets of the input eleven intervals → 2048 subsets → optimum 4 earliest finish 4 earliest start 3 shortest 4 fewest conflicts 1 three of the four match the optimum here, and two of those three are wrong rules

One instance, four rules, and the number that judges them

Core ideas

What this lesson establishes

Three ideas: what makes a rule greedy, why a selection's size means nothing until its legality has been checked, and why an optimum that is computed rather than asserted changes what a lab can prove.

A greedy rule is an order, plus a refusal to reconsider

Fix an order on the input. Walk it once. Take the current item if taking it keeps the answer legal, and otherwise skip it forever. That is the whole pattern, and every difference between the four rules on this page is the order — earliest finish time, earliest start time, shortest first, fewest conflicts first. Nothing is ever put back, which is what makes these algorithms fast and what makes them capable of being wrong: a single bad early choice is never repaired.

A bigger selection may not be a legal one

Two intervals are compatible when they do not overlap, and this course reads 3-8 as the half-open span from 3 up to but not including 8, so 3-8 and 8-11 both fit. A rule that returned six overlapping intervals would print a larger number than a rule that returned four legal ones, and the number alone cannot tell you which happened. So the panel runs intervalsDisjoint on every selection before it prints its size. On all four of the lab's instances every rule's selection passes that check — the column reads yes throughout — which is a measurement, not a reason to remove the check.

An enumerated optimum turns a claim into a computation

Because a greedy rule commits and never revisits, its answer on a small instance can be put beside the best of every subset. The panel does exactly that: eleven intervals, 2¹¹ = 2048 subsets, each tested for feasibility, and the largest feasible one reported with its members. So the sentence on the screen is never “greedy got four”. It is “greedy got four and the best of the 2048 is four, and here are its members” — or, on another instance, “greedy got one and the best of the eight is two, and here is the pair”.

The material

Four rules, one instance, and a number that settles it

The problem, the four orders, what each one selects, and why three correct answers on one input establish nothing about three of the rules.

Definition · Interval scheduling

Given n intervals, each a half-open span [s, f) with f > s, select as many as possible so that no two of them overlap. A selection is feasible when its intervals are pairwise disjoint, and the optimum is the largest feasible selection. Intervals that merely touch — one finishing exactly where the next starts — do not overlap.

The lab opens on eleven intervals, labelled in the order they are typed: A 1-4, B 3-5, C 0-6, D 5-7, E 3-9, F 5-9, G 6-10, H 8-11, I 8-12, J 2-14, K 12-16. The labels are what every table names, so one interval can be followed through four different orderings of the same instance.

Definition · The four rules

Earliest finish sorts by f and sweeps. Earliest start sorts by s. Shortest first sorts by f - s. Fewest conflicts first counts, for each interval, how many others it overlaps in the full instance, sorts by that count, and sweeps. Each rule then walks its own order once, taking an interval when it starts no earlier than the last one taken finished.

That last clause is the implementation, and it is worth reading twice. The sweep keeps one number — the finish time of the most recently taken interval — and compares each candidate against it. For the earliest-finish order that is the same thing as compatibility with everything already chosen, because the chosen finish times only increase. For the other three orders it is not, and the difference shows up below.

Example · Eleven intervals, four answers

Earliest finish selects A D H K, four intervals. Earliest start selects C G K, three. Shortest first selects B D H K, four. Fewest conflicts selects K alone, one. All four selections are feasible, checked pairwise. The best of the 2048 subsets is four, attained by A D H K. So two rules match the optimum, one is one short, and one is three short — on this instance.

The interesting entry there is shortest-first. It gets four, which is optimal, and it is not a correct rule. The lab ships the three intervals that prove it: 0-5, 4-6, 5-10. Shortest-first takes the two-unit interval in the middle, which blocks both of the others, and finishes with one where the best of the eight subsets is two. One instance where a rule is wrong is all it takes, and one instance where it is right is worth nothing at all.

Each losing rule has an instance built for it

Earliest start fails on 0-10, 1-2, 3-4, 5-6, 7-8: the interval that starts first occupies the whole day, the rule takes it and stops at one, and the optimum is four. Fewest conflicts fails on 0-2, 2-4, 4-6, 6-8, 1-3, 3-5, 5-7: it takes A and D, the two intervals with one conflict each, and returns two against an optimum of four. Earliest finish has no such preset, and the reason is not that nobody built one.

The fewest-conflicts instance repays a careful look, because the panel's own grey caption gets it wrong. That caption says taking the two ends “leaves the middle unusable”. The table directly above it names the optimum: A B C D, which is the two ends and the two middle intervals. The middle is perfectly usable. What loses the two intervals is the sweep: after A and then D the single finish-time pointer stands at 8, and B starting at 2 and C starting at 4 are both behind it. Where a caption and the table disagree, the table is the measurement.

The rule the panel runs, and the rule the textbooks state

Fewest-conflicts is usually stated as a rule that recomputes the conflict counts after each removal. The shipped implementation sorts once, by each interval's conflict count in the full instance, and then sweeps — the static-order variant. Both are wrong on some instance, the panel names the one it ran, and the figures on this page are the static one's. A lesson that quoted the dynamic rule's behaviour from a textbook while the page computed the static one's would be teaching a third thing that is neither.

Theorem · The earliest-finish rule is optimal on every instance

For interval scheduling, the selection produced by sorting on finish time and sweeping is a largest feasible selection, for every input. Not “usually”, and not “on the instances tried”.

That is a claim about all inputs and the lab cannot establish it. What the lab can do is the half that is checkable: for any instance you type, it computes the optimum by enumeration and reports whether the rule matched. The two proofs that close the other half — stays-ahead and the exchange argument — are the subject of the material that follows this page, and the second of them is performed rather than described.

Stays-ahead is already visible here. Write gᵢ for the finish time of greedy's i-th chosen interval and oᵢ for the optimum's, both in increasing order. On the opening instance greedy's finish times are 4, 7, 11 and 16, and the panel reports that it never falls behind at any step. The claim the proof makes is that gᵢ ≤ oᵢ for every i on every input, which is induction, not four numbers.

So the honest summary of this page is two sentences that do not say the same thing. Measured: on the instance shown, earliest finish and shortest first both reach the optimum of 4, earliest start reaches 3, fewest conflicts reaches 1. Proved: earliest finish reaches the optimum on every instance, and each of the other three has an instance on which it does not. The first sentence is a count on one input. The second is the bound, and nothing you can do to the controls will produce it.

Interactive

A greedy rule is right or it is not, and the optimum settles it

Four rules on one instance, each beside the best of every subset

Choose the instance, then choose the rule

The optimum is the best of every subset and knows nothing about any of the four rules. Switch rules on one instance to see which of them happen to be right here; switch instances with the rule fixed to see the same rule stop being right.

Instance

Intervals, written start-finish

Greedy rule

Intervals typed—

This rule selects—

The most any subset fits—

The selection is feasible—

Subsets the optimum searched—

Exchange argument survives—

An interval is 3-8: it occupies the time from 3 up to but not including 8, so 3-8 and 8-11 both fit. The table under the chart runs all four rules on the same instance; the one under that performs the textbook exchange argument one swap at a time and checks after every swap that the set is still feasible and still the same size.

Method

Judging a rule instead of admiring it

The order of these four matters: the last one is what turns an observation into a finding.

Read the feasibility column before the size column

A selection's size is meaningless until the selection is legal. The panel checks pairwise disjointness and prints the verdict; on every shipped instance it reads yes for all four rules, and that is a fact you confirm rather than assume.

Put the optimum beside the rule, every time

Never write down what a rule selected without writing down what the best subset selected. The gap is the only thing that matters, and on this problem the gap is computed for you from an enumeration that has no idea the rules exist.

Change the instance with the rule held fixed

This is the experiment that separates the rules, because switching rules on one instance cannot. Leave the rule on shortest-first and move through the four instances: 4, 1, 4 and 4 against optima of 4, 2, 4 and 4. The single 1 is the finding.

Name the step where a wrong rule went wrong

Not “it is a heuristic”. On the shortest-first trap the rule takes the middle interval and blocks two; on the earliest-start trap it takes the interval spanning the whole day. Each failure is one identifiable commitment that could not be undone.

Rules, optima, and what a match is worth

Score 0 / 0

Choose the answer you can justify.

The earliest-finish sweep on the opening instance, by hand

Sort the eleven intervals by finish time, then walk the sorted list once carrying a single number: the finish time of the last interval taken. Take the current interval when its start is at least that number.

sorted by finish A 1-4 B 3-5 C 0-6 D 5-7 E 3-9 F 5-9 G 6-10 H 8-11 I 8-12 J 2-14 K 12-16 interval start last finish decision A 1-4 1 - TAKE last = 4 B 3-5 3 4 skip C 0-6 0 4 skip D 5-7 5 4 TAKE last = 7 E 3-9 3 7 skip F 5-9 5 7 skip G 6-10 6 7 skip H 8-11 8 7 TAKE last = 11 I 8-12 8 11 skip J 2-14 2 11 skip K 12-16 12 11 TAKE last = 16 selection A D H K finish times 4, 7, 11, 16 feasible yes, pairwise optimum 4, the best of 2048 subsets, attained by A D H K

Four takes and seven skips, one pass, no interval reconsidered. The seven skips are where a greedy algorithm earns its speed and risks its correctness: C 0-6 was rejected at step three and never looked at again, although at that moment nothing had been chosen that conflicted with it except A.

Notice that the enumerated optimum came back as A D H K — greedy's own answer. That is a coincidence of this instance and it matters in the material that follows, where the exchange argument has nothing to do when the optimum the search returns is already the rule's answer. Switch the rule to shortest first, which selects B D H K, and the same enumeration still returns A D H K: now the two differ in one interval.

For a faded rehearsal, predict the sweep for earliest start on the same eleven before running it. The supplied first move is this: sorted by start the list opens C 0-6, A 1-4, J 2-14, and the rule takes C, which finishes at 6 and rules out five of the remaining ten. Say what it ends with and how many that is, then check — and then say which single interval you would delete to make earliest start optimal here.

Common mistakes

Reading a match with the optimum as a proofThe most common error on this page, and the whole reason the page exists. Three of the four rules reach 4 on the opening instance and only one of them is a correct algorithm. Any sentence of the form “the rule works, I checked it” is a statement about one input, and this course will keep asking which input.

Trusting a size without the feasibility columnGreedy rules on this problem cannot produce overlapping selections, because the sweep compares against the last finish time — but that is a property of the implementation, not of the word “greedy”. Hand-built selections, and rules written differently, can and do overlap, and the only defence is a pairwise check on the selection you are about to believe.

Assuming the shipped fewest-conflicts rule is the one in your textbookThe panel runs the static-order variant: conflict counts are taken once, in the full instance, and never recomputed. The dynamic version recounts after every removal and is a different algorithm with different output. The page says which it ran; reading the label and supplying the other algorithm's behaviour from memory produces figures that match neither.

Check your understanding

✓

Finish when you can take a selection rule you have not seen before and produce, from the lab, either a proof obligation or a counterexample.

You should be able to state the half-open convention and say why 3-8 and 8-11 are compatible, run any of the four sweeps by hand, explain why the enumerated optimum is a different kind of object from a rule's output, and — given a rule that matched the optimum on the instance in front of you — say precisely what remains unproved.

Note: The two ways of closing that gap are the material that follows. Stays-ahead is the one already on this page: greedy's i-th finish time never exceeds the optimum's, checked here step by step and proved by induction. “The Exchange Argument” is the other, and it is not described there but performed — an optimum turned into greedy's own answer one swap at a time, with the set rechecked after every swap.