Greedy Algorithms: When Taking the Obvious Choice Actually Works

Greedy algorithms have this reputation for being "easy" — just pick the best option at each step and you're done. And honestly, when they work, they're elegant. The code is short, the logic is clean, and the time complexity is usually great.

The problem is knowing when they work.

What Makes a Problem Greedy-Solvable

Two properties need to hold:

Greedy choice property — a locally optimal choice leads to a globally optimal solution. You never need to reconsider a decision you've already made. This is the big one, and it's the one that trips people up. Optimal substructure — the optimal solution to the problem contains optimal solutions to its subproblems. This one shows up in dynamic programming too, so it's not unique to greedy. But both need to be present.

If only optimal substructure holds but not the greedy choice property, you probably need DP instead.

The Classics

Activity Selection

You have a set of activities with start and end times. Pick the maximum number of non-overlapping activities.

The greedy approach: sort by end time, always pick the activity that finishes earliest (as long as it doesn't conflict with the last one you picked).

Why it works: by finishing as early as possible, you leave the most room for future activities. No future information could make an earlier-finishing activity a worse choice.

Fractional Knapsack

You have items with weights and values, and a knapsack with a weight limit. You can take fractions of items. Maximize total value.

Sort items by value-per-weight ratio, take as much of the highest-ratio item as you can, then move to the next. Straightforward and correct.

Note: this does NOT work for 0/1 knapsack (where you can't take fractions). That's the classic example of greedy failing — you need DP for the integer version.

Huffman Coding

Build an optimal prefix-free encoding by repeatedly merging the two lowest-frequency characters. This is greedy because at every step, you're making the locally optimal merge, and it provably leads to the global optimum.

The proof relies on the fact that less frequent characters should have longer codes, and the two least frequent characters should differ only in their last bit. It's one of the more satisfying correctness proofs in algorithms.

Coin Change (The Trap)

Given coin denominations and a target amount, find the minimum number of coins.

With US denominations (1, 5, 10, 25), greedy works perfectly — always pick the largest coin that fits. But change the denominations to {1, 3, 4} and try to make 6. Greedy picks 4+1+1 = 3 coins. Optimal is 3+3 = 2 coins.

This is the example every interviewer has in their back pocket. The greedy choice property doesn't hold for arbitrary denominations. You need DP.

How to Tell If Greedy Works

There's no universal shortcut, but here are some heuristics:

Exchange argument — the most common proof technique. Assume you have some optimal solution that differs from the greedy solution. Show you can "exchange" a non-greedy choice for the greedy choice without making things worse. If you can always do this, greedy is optimal. Try to find a counterexample — before committing to greedy, spend a minute trying to break it. Small inputs where the greedy choice leads to a suboptimal result. If you find one, it's not greedy. Known problem patterns — interval scheduling, Huffman-style merging, minimum spanning trees (Kruskal's, Prim's), shortest paths (Dijkstra's with non-negative weights). These are proven greedy problems. If your problem reduces to one of these, you're good. The gut check fails more than you'd think — greedy feels right on a lot of problems where it's wrong. The 0/1 knapsack feels greedy. The traveling salesman feels greedy (nearest neighbor heuristic). But they're not. Trust proofs, not intuition.

Common Interview Greedy Problems

• Jump Game — can you reach the end? Track the farthest reachable index.
• Gas Station — circular route, find valid starting point. Track running surplus.
• Task Scheduler — schedule tasks with cooldowns. Greedy by most frequent task first.
• Partition Labels — greedily extend each partition to include all occurrences of its characters.

These show up constantly, and the pattern is usually: sort or scan linearly, maintain some running state, make an irrevocable choice at each step.

Greedy vs DP vs Brute Force

If greedy works, use it — it's almost always faster and simpler. If you're not sure, try greedy first with small examples. If it breaks, move to DP. If the problem has no overlapping subproblems (each subproblem is unique), you might be looking at divide and conquer instead.

The skill isn't just knowing greedy algorithms. It's recognizing when a problem has the greedy choice property and when it doesn't. That recognition comes from practice — working through problems where greedy works and problems where it spectacularly fails.

You can practice greedy problems interactively on CodeUp, where you'll get immediate feedback on whether your greedy approach actually produces optimal results or just looks like it does.