How do you know a greedy choice is safe and not merely plausible?

Short answer

A greedy choice is safe when you can show at least one optimal solution contains it, usually via an exchange argument that swaps an optimum's first choice for yours without losing anything.

Mention exchange argument where it changes the risk, the owner, or the next check.

Safe means something precise

A greedy algorithm commits at every step and never revisits. That is sound only if each choice satisfies the greedy-choice property: there exists an optimal solution containing the choice you just made. Look at the shape of that claim. It does not say your choice appears in every optimum, and it does not say your choice scores best on some heuristic. It says one optimum agrees with you, which is exactly enough for induction to carry the argument to the end.

The second half is optimal substructure. Once you commit, what remains must be a smaller instance of the same problem, so the same argument applies again. When both hold you get a proof by induction on steps; when the second fails, greedy can be safe on the first move and unsafe on the third.

Doing the exchange, on interval scheduling

Take n activities each with a start and a finish, and select as many pairwise non-overlapping activities as possible. The greedy rule is to repeatedly take the compatible activity that finishes earliest.

Here is the exchange. Let g be the activity with the globally earliest finish, and let O be any optimal set, listed in finish order, with first element o1. Since g finishes earliest of all activities, finish(g) <= finish(o1). Now swap g in for o1. Every other activity in O starts at or after finish(o1), which is at or after finish(g), so none of them collides with g. The swapped set is feasible and exactly the same size, therefore also optimal, and it contains g. Recurse on the activities that start at or after finish(g).

That is the entire method, and it generalises: assume an optimum that disagrees with you, exhibit a swap that makes it agree without making it worse, conclude your choice was never the thing that cost you anything. Three sentences of that in a coding round is worth more than a tidy implementation.

// Sorting by finish time is not a convention - it is the induction order the proof uses.
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));

int count = 0;
int lastFinish = Integer.MIN_VALUE;
for (int[] iv : intervals) {
    if (iv[0] >= lastFinish) {   // >= because [s, f) is half-open: touching is not overlapping
        count++;
        lastFinish = iv[1];      // the only state the recursion needed
    }
}

Time is O(n log n), all of it in the sort; the scan is linear and uses one variable of extra space. Note that the loop is the recursion from the proof flattened: lastFinish is the "starts at or after finish(g)" filter, applied lazily.

Two places the same instinct misfires

Coin change with denominations {1, 3, 4} and a target of 6. Largest-first gives 4 + 1 + 1, three coins; the optimum is 3 + 3, two coins. Try the exchange and it visibly fails: there is no way to take an optimum containing two 3s and swap a 4 into it without ending up with more coins. Be careful how you phrase this, though, because "greedy fails on coin change" is too strong. Greedy is optimal on the denominations most currencies actually use, and determining whether a given system is canonical is its own computation rather than something you can eyeball.

The second is 0/1 knapsack ordered by value density. Capacity 10, with items A (weight 6, value 7), B (weight 5, value 5) and C (weight 5, value 5). Densities are about 1.17, 1.0 and 1.0, so greedy takes A, has 4 capacity left, cannot fit anything else, and stops at 7. Taking B and C fills the sack exactly for 10.

The exchange breaks here because removing A leaves a fragment of capacity that no whole item can consume, so the residual problem is not the original problem on a smaller input; it is a problem shaped by what you already spent. Allow fractional items and the exchange works again immediately, because the leftover can always be filled with a slice of the next-densest item.

The distinction interviewers are grading

Almost everyone who answers this badly does so the same way: they validate on examples. "I tried several inputs and greedy matched brute force" is evidence, and it is the kind of evidence that survives right up to the input the interviewer has ready. The tell is an answer that gives the rule, then the complexity, and never touches why the rule is allowed to skip the alternatives.

The recovery when you cannot find an exchange is to say so and switch. A failed exchange is informative: the reason greedy broke on 0/1 knapsack is that remaining capacity matters, and remaining capacity is precisely the second dimension of the dynamic programming state. The failure hands you the state.

State the greedy-choice property before you write the loop, and if you cannot sketch the swap in a sentence or two, treat that as evidence the problem is dynamic programming rather than as a gap in your explanation.

---

© 2026 Preptima. Originally published at preptima.com.