I have lost count of the times I have watched a candidate stare at a problem, mutter "this feels greedy", write a one-liner, and then get destroyed on the first failing test case. Greedy is seductive because it is short, it runs fast, and when it works it produces code that fits on a Post-it. The trouble is that the failure mode is silent. A wrong greedy passes ten test cases and crashes on the eleventh, and you have no idea why because the reasoning was vibes-based to begin with.

I want to push back on the common interview-prep advice of "try greedy first, fall back to DP if it fails". That advice is fine if you can prove the greedy is correct in 60 seconds. If you cannot, you should not write it, even speculatively, because a wrong greedy that almost works is much worse than a slow DP that definitely works. The contrarian position of this article is: greedy needs a proof, every time, and the proof template is short enough that you can run it in your head.

The two heuristics that actually decide it

There are two formal frameworks that tell you when greedy is safe. They are both real CS, both teachable in an interview-bus-ride window, and either one is enough on its own.

Exchange argument. Take any optimal solution. Show that you can transform it, step by step, into the solution that the greedy algorithm produces, without ever making it worse. If that transformation always exists, the greedy solution is at least as good as any other, so it is itself optimal. The argument lives or dies on whether you can write down the swap step concretely.

Matroid structure. A matroid is a pair (E, I) of a ground set and a family of "independent" subsets that obeys two axioms: (1) every subset of an independent set is independent; (2) for any two independent sets where one is larger, the larger one contains an element you can add to the smaller while keeping it independent (the exchange property). The classical result is that for any weight function on E, the greedy algorithm finds the maximum-weight independent set. If your problem can be cast as picking elements from a ground set under matroid constraints, greedy is mechanically correct.

For interview-pace work, exchange-argument is the practical tool. Matroid structure is the framework that explains why exchange-argument works for so many problems and gives you a formal certificate when you need one. The questions on the test are almost always solvable with the exchange argument; the matroid framing is for when you have to defend the result.

Walking exchange-argument on activity selection

Activity selection: given n activities each with a start and end time, pick the maximum number of non-overlapping activities. The greedy is "pick the activity with the earliest end time, remove all activities that conflict with it, repeat". Why is this correct?

Let G be the set the greedy produces. Let O be any optimal solution. Sort both by end time. If G[0] has the earliest end time globally, then either G[0] = O[0] or G[0] ends no later than O[0]. In the second case, swap O[0] for G[0] in the optimal solution: the new set is still non-overlapping (because G[0] ends earlier, so anything that didn't conflict with O[0] doesn't conflict with G[0]) and the same size. Repeat for G[1], G[2], etc. After |G| swaps the optimal solution and the greedy solution match, so |O| = |G|. The greedy is optimal.

The shape of that argument is the template. Pick the first greedy choice. Show you can swap it into any optimal solution without making it worse. By induction, the greedy and the optimal coincide.

function selectActivities(activities) {
    const sorted = [...activities].sort((a, b) => a.end - b.end);
    const result = [];
    let lastEnd = -Infinity;
    for (const a of sorted) {
        if (a.start >= lastEnd) {
            result.push(a);
            lastEnd = a.end;
        }
    }
    return result;
}

Nine lines. The proof is the part that takes work, not the code. Skip the proof and you skip the right to be confident.

Why coin change breaks the greedy intuition

Coin change is the classic counterexample. Given coins [1, 5, 10, 25] (US denominations) and a target 30, the greedy "take the largest coin that fits" gives 25 + 5 = 2 coins, which is optimal. Given coins [1, 6, 10] and target 12, greedy gives 10 + 1 + 1 = 3 coins, but 6 + 6 = 2 coins is better. Same algorithm, same shape of input, completely different outcome.

Why does greedy work for one and fail for the other? US coin denominations form what number theorists call a "canonical coin system": for every target, the greedy solution is optimal. The system [1, 6, 10] is not canonical. There is no quick syntactic test you can run on the denominations to know in advance which case you are in (the test exists but it is non-trivial).

The practical lesson: even when the problem looks like activity selection on the surface ("pick items to optimise something"), the structure of the cost function matters. For activity selection, every chosen activity reduces the remaining time window by exactly end - start, and the greedy choice never wastes any of that reduction. For coin change, picking a 10 "costs" 10 from the target, but it might leave a remainder that costs more in small coins than picking two 6s would have. The exchange argument fails because the swap introduces wasted denomination.

Coin change with coins [1, 6, 10] for target 12

Greedy:    10 -> 1 -> 1                (3 coins)
Optimal:    6 -> 6                     (2 coins)
The exchange (replace one 10 with two 6s) makes the count larger, not smaller.

When the swap is not safe, greedy is not safe, and you fall back to DP.

A comparison table I keep on a sticky note

The pattern in the "yes" column: there is always a swap that makes the optimal solution match the greedy choice without loss. The pattern in the "no" column: the cost function or the constraint structure makes the swap unsafe.

My actual decision flow on a problem

When I see a problem and "greedy" comes to mind, I run this checklist before writing code:

1. Can I phrase a single greedy choice (e.g., "always pick the X with the smallest Y")?
2. Can I write down what the swap would be, in plain English, between the greedy choice and any other choice?
3. Does the swap preserve feasibility (the resulting solution is still valid)?
4. Does the swap preserve or improve the objective?

If step 2 or 3 or 4 fails, I do not write the greedy. I move to DP. If all four pass, I write the greedy with a one-line comment explaining the swap, because future-me will read the code in a year and need to recover the proof.

The version of step 1 I get most often is "sort by something, then iterate". If I cannot tell you what the something is and why sorting by it is the right key, I cannot do step 2, and I should not be writing greedy code.

The reluctant defence: when DP is too slow and greedy is what you have

This is the counter-stance. There are problems where the optimal DP is O(n^2) or O(n * W) and the input is large enough that you cannot afford it. Set cover, minimum vertex cover, the metric travelling salesman, max-cut: these are NP-hard, and the practical answer is a greedy approximation that does not produce optimum but produces something with a provable approximation ratio. Set-cover greedy is H(n)-approximate (about log n times worse than optimum), and it is the best polynomial algorithm we know unless P = NP. Christofides for metric TSP is 1.5-approximate.

These are greedy algorithms that work, but the proof shape is different: you are not proving optimality, you are proving a worst-case ratio. The exchange argument becomes "the greedy choice is at most a factor k worse than the optimal at every step". The activity-selection proof is a degenerate case of this where k = 1. When you read a paper that says "a 2-approximation for vertex cover", what you are reading is an exchange-argument bounded by a factor.

For production code on hard problems, I am happy to ship a greedy with a known approximation ratio if the speed gain is real and the optimum is unreachable. What I will not ship is a greedy with no proof, on the hope that the test cases I have happen to be the easy ones. The cost of that hope is the silent failure I opened the article with, and it is exactly what makes greedy hard to debug in production.

Greedy is fast, short, and elegant when it is right. It is treacherous when it is wrong, because the failure mode is data-dependent and your tests probably do not cover it. The exchange argument is the cheapest correctness check you can run before you commit to greedy, and matroid structure is the formal backstop when you need one. Run the check. If it passes, write the nine-line solution and feel good about it. If it fails, write the DP, accept the extra O(n) factor, and stop hoping.