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 ten 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, and Stable Matching pairs up two equal-size groups. 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 ten for my problem." It's "which of four trust tiers does a greedy idea — this site's ten, or a new one you're eyeing for your own problem — fall into."
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)? Seven of the ten entries can, and are exactly correct, always — though for one of the seven, "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.
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.
Coin Change breaks the pattern above in a way none
of the four 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.
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.
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.
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.
| Entry | Tier | Proof shape | What 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 |
| 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 |