What is a greedy algorithm?
A greedy algorithm makes the locally best choice at every step and never reconsiders it — no backtracking, no looking ahead. It only lands on the true optimal answer when the problem has the right structure underneath; without that structure, it gives a plausible-looking wrong answer with total confidence.
- Greedy choice
- The obviously-best option taken right now, locked in forever
- Sort-then-sweep
- Sort by a key first, then take the obviously-best option in a single pass
- Exchange argument
- Proof that swapping in the greedy choice can never make the final answer worse
Why greedy at all?
Picture a cashier making change. They don't sit down and plan every possible combination of coins — they just grab the biggest coin that still fits under the amount owed, then repeat.
No backtracking, no comparing alternatives. One pass, one obviously-best choice per step, and for ordinary coins it lands on the fewest coins possible every time.
Every coin taken is the biggest one that still fits. No coin is ever un-picked.
What kinds of problems does it solve?
Three common shapes. Each one makes one obviously-best decision per step and never looks back — what changes is what "best" means and whether the input needs sorting first.
Fit the most non-overlapping meetings
Sort meetings by their finish time. Walk through them once, keeping any meeting that starts after the last one you kept ends. Finishing earliest always leaves the most room for what comes next.
A meeting is kept only if it starts at or after the last kept meeting's end.
Grab every price increase
Compare each day's price to the day before. Any time it went up, bank that difference as if you'd bought the day before and sold today. No need to plan ahead — every uptick is worth taking.
Price up from yesterday → bank it. Price down → nothing to take.
Match the smallest sufficient resource
Sort both the needs and the resources. Give each child the smallest cookie that still satisfies them — handing out anything bigger would waste a cookie a fussier child might have needed.
Cookie big enough → hand it over, move to the next kid. Too small → skip it.
Two types
Underneath, greedy comes in two justifications: sort first and sweep once, or prove that swapping in the greedy choice can never make the final answer worse than any alternative would have.
Sort-then-sweep
Sort by a key that makes the "obviously best" option visible, then make a single pass taking it every time. Most interval and scheduling problems reduce to this shape.
One pass, sorted once. Every kept meeting starts after the last one ends.
function maxNonOverlapping(intervals: [number, number][]): number {
const sorted = [...intervals].sort((a, b) => a[1] - b[1]); // sort by finish time
let count = 0;
let lastEnd = -Infinity;
for (const [start, end] of sorted) {
if (start >= lastEnd) { // fits after the last one kept
count++;
lastEnd = end;
}
}
return count;
}
Exchange argument
At each step, prove that swapping in the locally-best choice can never make the final answer worse than any other choice would have. Coin change with ordinary coins leans on exactly this proof.
A dime beats two nickels here — swapping never helps with canonical coins.
function fewestCoins(amount: number, coins: number[]): number {
const sorted = [...coins].sort((a, b) => b - a); // largest coin first
let remaining = amount;
let count = 0;
for (const coin of sorted) {
while (remaining >= coin) { // take the biggest coin that still fits
remaining -= coin;
count++;
}
}
return remaining === 0 ? count : -1; // only optimal for canonical coin systems
}
Where it works — and where it breaks
Greedy leans on a quiet assumption: that the local choice really does compose into the global optimum. With ordinary coins it does. Swap in an unusual coin system and the exact same strategy gives a confident, wrong answer.
Works with ordinary coins
25, 10, 5, 1 — each denomination is more than double the next one down, so grabbing the biggest coin that fits can never be beaten by a smaller one. 30¢ becomes 25 + 5, two coins, correctly minimal.
Breaks with unusual coins
Coins {1, 3, 4} making 6¢: greedy grabs 4, then has to fill the last 2¢ with two pennies — 3 coins total. The real optimum is 3 + 3, just 2 coins. Greedy never even considers it.