Taking the Best Bite Now and Never Looking Back
A strategy that refuses to reconsider is fast, simple, and usually wrong — unless the problem has two specific properties. Here is how to tell, and how to catch it when it lies to you.
Visual style: notebook-3d — generated with gpt-image-2
Core Concept
A greedy algorithm makes the locally optimal choice at each step and never revises it. There is no backtracking, no exploring of alternatives, no memo table. That is the whole design — and it is why the cost is typically O(n log n), dominated by the sort, rather than exponential.
The interesting question is never how greedy works. It is when it is allowed to work. And that has a precise answer, not a vibe.
Key Components
Greedy-choice property
A globally optimal solution can be built from locally optimal choices. The best move now is compatible with some best answer overall.
Optimal substructure
After you commit to a choice, what remains is the same problem, smaller. Solve it the same way and you are still on track.
The sort key
The key you sort by is the algorithm. Change the key and you change the answer — usually from correct to quietly wrong.
The exchange argument
The proof shape: show you can swap any optimal solution's choice for the greedy one without making it worse. No proof, no guarantee.
How It Works — Interval Scheduling, the Clean Case
- You are given a set of intervals (meetings, jobs, bookings) and want the maximum count of mutually compatible ones.
- Sort all intervals by earliest finish time. This sort is where the O(n log n) goes.
- Walk the sorted list. Take every interval that does not overlap what you have already taken.
- Never reconsider a taken interval. When the walk ends, you provably hold a maximum-size compatible set.
- The reason it holds: finishing earliest leaves the most room for everything after it. That sentence is the exchange argument in plain English.
Now change one thing. Sort the identical problem by earliest start time, or by shortest duration, and you get wrong answers — a single long early interval can eat the slot where three short ones fit. Same code, same data, different key, broken guarantee.
Where It Fails — and Why You Won't Notice
Greedy is usually wrong, and the failure is silent
It does not crash. It does not warn. It returns a plausible, valid, suboptimal answer that passes every sanity check you would casually run.
The standard counterexample is coin change with denominations 1, 3 and 4:
make 6greedy → 4 + 1 + 1 = 3 coins
optimal → 3 + 3 = 2 coins
Greedy grabs the 4 because it is the biggest coin that fits, and then it cannot take the move back. The same shape breaks 0/1 knapsack: sorting by value-per-weight can miss the best combination entirely, because you cannot take fractions of the item you skipped.
The test: brute-force small inputs, diff against the greedy answer. If they ever differ, the greedy-choice property does not hold for your problem and no amount of tuning the key will save it.
Real-World Applications
- Huffman coding — repeatedly merge the two least-frequent symbols. Provably optimal prefix codes; greedy with a real proof behind it.
- Dijkstra and Prim/Kruskal — shortest paths and minimum spanning trees are greedy algorithms whose correctness rests on exactly these two properties.
- Meeting-room and job scheduling — the earliest-finish-time rule ships in real calendar and batch-scheduling systems.
- Cache eviction and load shedding — take the cheapest local decision now; accept a bounded loss of optimality for O(1)-ish cost.
- Where teams get burned — bin-packing servers, currency handling in non-canonical denominations, and knapsack-shaped budget allocation, all of which look greedy-safe and are not.
Checkpoint — answer before you move on
- Name the two properties a problem must have before greedy is safe, and say in one sentence what each one guarantees. One is about the choice being compatible with optimality; the other is about what is left over.
- Interval scheduling sorts by earliest finish time. Explain why sorting by shortest duration instead can produce a smaller answer. Construct a three-interval example on paper where the shortest one blocks two others.
- With coins 1, 3 and 4, greedy pays 6 as 4+1+1. What is the optimal payment, and what would you actually run to discover that greedy was wrong here without knowing the counterexample in advance? The second half is the generalisable skill: the answer is a procedure, not a fact.