Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Greedy Strategy

Every other guide on this site compares algorithms that compete for the same job — six sorts that all sort an array, five spatial structures that all index points. The twelve Greedy entries don't: Huffman Coding builds codes, Activity Selection schedules a single resource, Interval Point Cover finds the fewest points touching every interval, Interval Partitioning finds the fewest parallel resources to run every interval at all, Fractional Knapsack fills a divisible container, Coin Change makes change, Job Sequencing schedules a resource with deadlines attached, Set Cover covers a universe, Greedy Coloring assigns colors to a graph's vertices, Stable Matching pairs up two equal-size groups, Minimizing Maximum Lateness schedules a single resource with deadlines but no notion of missing one outright, and Boyer–Moore Majority Vote asks whether any candidate holds a strict majority of a list of votes at all. Nobody picks between them for one task. What they share instead is a question that has nothing to do with the task: each one commits to whatever looks locally best right now and never reconsiders — so how do you know that actually lands on the true optimum, rather than just looking like it should? This guide isn't "which of these twelve for my problem." It's "which of four trust tiers does a greedy idea — this site's twelve, or a new one you're eyeing for your own problem — fall into."

Three questions, four tiers

Can greedy's choice be proven optimal against every possible input — either by an exchange argument (show that any solution disagreeing with greedy's first move can be rearranged to agree with it, at no cost), by matching a lower bound to an upper bound (show nothing can beat some number, and greedy never exceeds it), or by showing no proposal is ever wasted (a rejection can only happen in favor of someone at least as good, so nothing better was ever actually available), or by an adjacent-swap argument (show that exchanging any two out-of-order neighbors can only help, so a fully sorted arrangement is at least as good as anything else), or by a cancellation-pair argument (show that any two disagreeing votes cancel out one-for-one, so a true majority — more than half — can never be fully erased)? Nine of the twelve entries can, and are exactly correct, always — though for one of the nine, "exact" doesn't pin down a single right answer; see below. If not, does correctness depend on the specific numbers you were handed rather than the shape of the problem itself? One entry is exactly correct on some inputs and genuinely wrong on others, with no way to tell which from the problem statement alone. And if the problem is NP-hard, so no greedy rule — or any polynomial rule — can be exact on every input, is there instead a provable ceiling on how far off greedy can land? One entry trades "always exact" for "always within a proven factor," which is a different kind of guarantee, not a weaker claim dressed up. And if no such ceiling can be proven either — some greedy rules don't even get that — is the gap bounded by anything at all, or can it grow without limit as the input grows? One entry has no ceiling whatsoever: its only guarantee bounds its own output, not its distance from the truth.

Tier 1: exact, by exchange argument (mostly)

Huffman Coding, Activity Selection, Interval Point Cover, Fractional Knapsack, and Job Sequencing are all exactly correct on every input, and all five proofs have the same skeleton: take any optimal solution, show it can be rearranged to match greedy's next move without getting worse, then note the remaining problem has the identical shape — so the argument reapplies to greedy's second move, third, and so on. The five differ in what gets exchanged and why the exchange is free. Interval Partitioning is also exactly correct on every input, and belongs in this tier by outcome, but its proof isn't an exchange argument at all — see below.

Huffman's proof is about tree shape, not a swap between two named items: in any optimal prefix code, the two rarest symbols must already be siblings at the tree's deepest level, because moving them there from anywhere shallower can only shrink the total encoding. Merge them and recurse on the smaller tree. On the site's own abracadabra example this lands on 23 bits against a 33-bit fixed-width baseline for the same 5-symbol alphabet — a saving that traces directly back to that one structural fact, not to anything about this specific message.

Activity Selection's proof swaps one concrete activity for another: whichever optimal schedule you're handed, if it doesn't already include the single earliest-finishing activity, swapping that activity in for whatever occupies its slot can't create a conflict, because everything else in the schedule already tolerates that slot's original occupant finishing later. On the site's 11-activity set this proof cashes out as 4 activities, matched exactly by brute force — and the guide's companion pitfall is that other plausible sort keys (earliest start, shortest duration) have no such swap available to prove them safe, and each one provably falls short on the same or a nearby dataset (3 activities instead of 4; 1 instead of 2).

Interval Point Cover's proof is Activity Selection's swap run from the opposite end of the sort: whichever optimal point set you're handed, if it doesn't already contain the end of whichever interval ends earliest of all, sliding its nearest point up to that end can't uncover anything that point was covering — every interval that point stabbed has its own end at least as large as the earliest end, by definition of "earliest," so it still contains the slid-up point too. On the demo's eight-interval set this proof cashes out as 3 points, matched exactly by brute force — and the guide's companion pitfall is that placing the point at each interval's start instead of its end has no such swap available (67.5% of 10,000 random trials come up short), while sorting by start instead of end breaks even more fundamentally, producing a point set that misses intervals entirely on 71.5% of the same trials.

Fractional Knapsack's proof is an ε-transfer: if an optimal solution ever leaves capacity of a higher value-per-weight item untaken while taking a lower-ratio one, shifting an arbitrarily small amount of weight from the lower-ratio item to the higher-ratio one strictly increases value without changing total weight — a contradiction. That argument depends entirely on being able to move an arbitrarily small amount, which is exactly what item divisibility buys and exactly what its sibling page 0/1 Knapsack doesn't have — see the checklist below for what happens when this same ratio rule is asked to run on indivisible items instead.

Job Sequencing needs two independent exchange arguments, not one, because it makes two decisions: which jobs run, and where in the timeline they land. The first claim — process jobs highest-profit-first — swaps the single best job into whatever slot it needs, the same shape as Activity Selection's swap. The second claim is different in kind: once profit order is fixed, placing each job in the latest slot it can still make (not the first slot found) is what's actually safe, because every unit-time job is indifferent to which of its legal slots it gets, so taking the latest one preserves the most flexibility for whatever job comes next. Getting either claim right without the other still costs real profit: placing jobs at their earliest legal slot instead of latest drops the default 5-job set from 270 to 240, and sorting by profit ascending instead of descending — wrong on the first claim, not the second — drops the classic 5-job textbook set from 142 to 61, rejecting the single highest-profit job on the list entirely.

Interval Partitioning's proof is a different shape entirely from the five above: not an exchange argument, but a lower bound matched to an upper bound. If D intervals are ever active at the same instant, no schedule can use fewer than D rooms — those D intervals pairwise conflict, so no two can share a room, independent of any algorithm. Greedy, processing by start time, never opens more than D rooms either: the only time it opens a new one is when every existing room is still genuinely busy, which is only possible if that many intervals are truly overlapping right then. Lower bound and upper bound meet at the same number, with nothing left to swap. On the demo's own eight-talk set this proof cashes out as 3 rooms, matched exactly by an independent overlap-depth sweep — and the guide's companion pitfall is that checking only the most recently used room for reuse, instead of every open one, stays valid but wastes rooms 70% of the time (6 rooms instead of 3 on that same set), while comparing a room's free time against the wrong endpoint of the new interval produces genuine double-bookings 85% of the time.

Stable Matching's proof is a third shape again, and the entry itself breaks something none of the six above do: greedy's choice here is irrevocable in only one direction (once a proposer commits to proposing, that proposal is never withdrawn), while the receiving side's acceptance stays provisional until the very end. The proof isn't a swap and isn't a bound-meets-bound — it shows no proposal is ever wasted: if a rejection happens, it's only because the receiver already has, or immediately takes, someone she likes at least as well, and she never trades down afterward, so nothing better was ever really on the table. That's enough to rule out any pair who'd rather elope than stay put, on every input, with no exception. But unlike the six entries above, "exact" here doesn't mean one right answer: more than one stable matching can exist for the same preferences, and Gale-Shapley's own rule guarantees only that whichever side proposes gets the best partner available in any of them, while the other side gets the worst. On the site's own 3-person example, men proposing and women proposing are both exactly correct, and land on two genuinely different matchings — the first Greedy entry where being exact and being unique come apart.

Minimizing Maximum Lateness's proof is a fourth shape, and the only one of the nine that works on a pair of adjacent items rather than a single substituted one: take any schedule with two adjacent jobs out of deadline order, and swapping just that pair can only lower (or match) the schedule's worst lateness, because the later-deadline job's new lateness is provably less than the earlier-deadline job's old lateness, and the earlier-deadline job's own new lateness can only drop. Repeat until no such inversion is left, and what's left is sorted by deadline — the same shape a bubble sort's own correctness proof uses, aimed at a scheduling order instead of a numeric array. On the demo's own 5-job set this proof cashes out as a max lateness of 6, matched exactly by brute force over all 120 orderings (only 2 reach it) — and the guide's companion pitfall is that two more-plausible-looking rules both fall short: shortest-processing-time-first, which ignores deadlines entirely, misses the true optimum on 84.6% of 20,000 random trials, and least-slack-first, which accounts for both numbers but conflates two different jobs' urgency into one subtraction, still misses 41.2% of the time.

Boyer–Moore Majority Vote's proof is a fifth shape, and the only one of the nine that isn't about scheduling, covering, or filling at all — it's a pure counting argument. Any two disagreeing votes the algorithm cancels against each other must be unequal by definition, so a candidate holding a strict majority (more than half the votes) can never be one half of a self-cancelling pair with a copy of itself — every cancellation that removes one of its votes has to spend one non-majority vote to do it, and there simply aren't enough of those to go around. On the page's own 10-vote election, the majority candidate holds 6 votes against only 4 spread across everyone else, so at most 4 of those 6 can ever be cancelled away, leaving at least 2 standing no matter what order the votes arrive in — confirmed live by the demo landing on the right candidate after three separate false leaders. Unlike the eight entries above, this one's "exact" comes with a condition attached: the cancelling pass alone only tells you who the majority would be if one exists; a second, explicit scan confirming that candidate really clears half the votes is not an optional cleanup step but the difference between a proof and a guess — skip it, and the algorithm reports a "majority" on every single input, including the 16,900 of 20,000 tested arrays that don't have one at all.

Tier 2: exact only for the right input — Coin Change

Coin Change breaks the pattern above in a way none of the nine Tier 1 entries do: whether "take the largest denomination that fits, repeat" is even correct depends on which denominations you were handed, not on the shape of the change-making problem itself. For U.S. currency {1, 5, 10, 25} a real exchange-argument proof does exist — a sequence of coin-for-coin swaps bounds any optimal solution to at most 4 pennies, 1 nickel, and 2 dimes, which pins down exactly one combination for any amount, and it's the one greedy computes. A denomination set with that property is called canonical; one without it isn't, and canonicity isn't visible from eyeballing the numbers. Change just one coin — {1, 15, 25} instead of {1, 5, 10, 25} — and greedy on amount 30 takes a 25 first, then falls back to five 1s (6 coins), where two 15s (2 coins) is the real optimum. Change it differently — {3, 5}, amount 11 — and greedy gets stuck with a leftover 1 and reports no solution at all, even though 3+3+5 is a valid 3-coin answer sitting right there. Worse, canonicity isn't even a property you can confirm from one example either way: the same set {1, 3, 4} fails on amount 6 (greedy: 3 coins, optimum: 2) and succeeds on amount 8 (greedy matches the optimum exactly) — it's a property of the whole system across every amount, not something a single trial run settles.

Tier 3: never exact, but bounded — Set Cover

Set Cover gives up on exactness entirely, for a structural reason the other five don't share: it's NP-hard, so no polynomial algorithm — greedy or otherwise — can be exactly correct on every input unless P=NP. What greedy trades in instead is a proven ceiling on how wrong it can be, and the proof pattern is different in kind from an exchange argument: rather than comparing greedy's choice against one specific alternative, it compares greedy's progress each round against the optimal cover's size alone, via pigeonhole — if R elements remain and some cover of size OPT covers all of them, one of that cover's sets must contain at least R/OPT of those elements, so greedy's own best-available pick that round is guaranteed to do at least as well. That single per-round guarantee compounds into a proven O(OPT·ln n) ceiling on the total sets greedy ever needs — on the site's own 10-element example, a true optimum of 2 sets bounds greedy to at most 5, and the actual run needs 3. Both facts are true at once: greedy is never exactly right on that instance (3 ≠ 2), and the gap is exactly the kind of gap the proof said to expect, not a bug. This is a genuinely different, and in one sense stronger, kind of promise than "exact when the input cooperates" — it holds unconditionally, on every input, forever; it just promises closeness instead of correctness.

Tier 4: never exact, and not bounded — Greedy Coloring

Greedy Coloring shares Set Cover's NP-hard excuse — finding the true minimum number of colors is exactly as hard as Graph Coloring's own backtracking search shows — but it doesn't share Set Cover's consolation prize. Its one guarantee, that it never uses more than Δ+1 colors (Δ being the graph's maximum degree), is a bound on greedy's own output, not on its distance from the true chromatic number. Those are different claims, and the gap between them can be made arbitrarily large: the site's own demo graph has a true chromatic number of 2 forever, no matter how large it grows, while a bad vertex order forces greedy to use exactly as many colors as vertices in each of its two groups — checked directly at group sizes 2, 3, 4, 5, 8, 10, and 20, always hitting Δ+1 exactly, every time. Set Cover's O(OPT·ln n) ceiling would never let a gap grow like that; nothing here is stopping it. Whether greedy coloring lands anywhere near the true minimum depends entirely on vertex order, which the algorithm itself has no way to choose well — it's not proven to do badly on any particular graph, but nothing proves it won't, either, and that absence of a proof is the whole point of this tier.

Testing a new greedy idea against these tiers

Before trusting a greedy rule you've just thought of — for a problem not already on this site — these four entries suggest a checking order, cheapest first. First, try to write the exchange argument down. Not "it seems like taking the best option now should work out," the actual swap: take an arbitrary solution that disagrees with your rule's first choice, and show concretely why swapping toward your rule's choice can't make it worse. If that swap genuinely goes through for every input, you're in Tier 1, and the five entries above are the pattern to model the writeup on. If the swap depends on some numeric property of your specific input — the way Coin Change's swaps only work because each larger denomination happens to be cheaply reachable from smaller ones in this exact system — you're in Tier 2 territory: the rule may still be worth using, but it needs cross-checking against a slower, definitely-correct method (brute force or dynamic programming) across a spread of realistic inputs before you trust it on a new one, the same way Coin Change's own demo always runs its greedy answer against a live DP comparison rather than asserting correctness once. If the underlying problem is NP-hard and no exact polynomial rule can exist at all, look for a pigeonhole- or exchange-style argument that bounds the *ratio* instead of eliminating the gap — Set Cover's proof pattern is the template, and the ceiling itself, not just "greedy seemed to do fine on my test cases," is what makes the result trustworthy on inputs you haven't tried. If even that ratio bound won't go through — if the only thing provable is a bound on greedy's own output, like Greedy Coloring's Δ+1, with nothing tying that back to the true optimum — treat the rule as a fast heuristic only, worth running for a quick answer but never for a guarantee, and say so plainly rather than borrowing Set Cover's confidence without its proof.

And if none of the four arguments above can be made to go through — no exchange proof, no identifiable special-input property, no ratio bound, not even an output-only bound — that silence is itself the answer, not a gap to shrug off. 0/1 Knapsack is this site's standing example: rank items by value-per-weight, exactly Fractional Knapsack's rule, and greedily fill the pack — on the same five-item, capacity-10 dataset both pages share, it takes Stove, Food, and Rope for value 21, while the real optimum (found by dynamic programming, confirmed by brute force) is 22. The rule isn't subtly miscalibrated; it's simply not correct here, because the one thing every Tier 1 proof above depends on — being able to move an arbitrarily small or exactly-right-sized amount to complete an exchange — stops being available the instant items can't be split. A greedy rule that merely "looks like" one of the four exact patterns above, without the specific structural fact that makes the exchange free, is exactly as likely to be Coin Change or 0/1 Knapsack as it is to be Activity Selection.

Side by side

EntryTierProof shapeWhat can go wrong
Huffman Coding 1 — always exact structural: rarest two symbols are always deepest siblings nothing; ties only change which symbol gets which code, never the total length
Activity Selection 1 — always exact swap in the earliest finisher, recurse nothing, for this exact rule; other sort keys (start time, duration) have no such proof and do fail
Interval Point Cover 1 — always exact swap in the earliest-end point, recurse nothing, for this exact rule; point-at-start is suboptimal, sort-by-start can miss intervals entirely
Fractional Knapsack 1 — always exact ε-transfer contradiction, enabled by divisibility nothing, as long as value really is linear in the fraction taken
Job Sequencing 1 — always exact two swaps: profit order, then latest-slot placement nothing, if both claims are applied; either alone still costs real profit
Interval Partitioning 1 — always exact lower bound (max overlap) meets upper bound (greedy never exceeds it) — no exchange nothing, for this exact rule; checking only the last room wastes rooms, comparing against the wrong endpoint double-books one
Stable Matching 1 — always exact, but not unique no proposal is ever wasted — a rejection only happens in favor of someone at least as good nothing, for stability itself; but which of possibly several stable matchings you get depends on who proposes, and locking an engagement irrevocably breaks stability outright
Minimizing Maximum Lateness 1 — always exact adjacent swap on any deadline inversion, repeat until sorted nothing, for this exact rule; shortest-processing-time-first ignores deadlines outright, least-slack-first looks informed but still fails
Boyer–Moore Majority Vote 1 — always exact, if verified cancellation pair: two disagreeing votes cancel one-for-one, so a true majority (>half) can't be fully erased nothing, once the required verification pass confirms the winner really clears half; skipped, it reports a "majority" unconditionally, wrong 100% of the time when none exists
Coin Change 2 — exact only for canonical inputs coin-for-coin swap bound, valid only for specific denominations silently suboptimal, or outright wrong ("impossible" when a solution exists), on non-canonical denominations
Set Cover 3 — never exact, provably bounded pigeonhole bound on per-round progress vs. optimal size essentially always lands above the true optimum; guaranteed to stay within O(ln n) of it
Greedy Coloring 4 — never exact, not bounded pigeonhole bound on colors used (Δ+1) — no bound on distance from the true minimum vertex order alone can force any color count up to Δ+1, however far that sits from the true chromatic number; checking only the most recent neighbor produces an outright invalid coloring