Saidul Islam RajibWhen greedy fails, and what to do instead
Recognising the failure, and the escalation path from greedy to DP to search.
Greedy fails when an early choice forecloses a better future — when the best first move is not part of the best overall solution.
The 0/1 knapsack
Capacity 10. Items: A (weight 6, value 30), B (weight 5, value 25), C (weight 5, value 25).
Greedy by value takes A, leaving capacity 4 and nothing that fits: 30.
Optimal takes B and C: 50.
Taking A was locally best and globally wrong. No sort order fixes this, because whether A belongs in the answer depends on what else fits after it — precisely the dependency greedy refuses to look at.
The escalation path
| Symptom | Move to |
|---|---|
| A single ordering makes each choice safe | Greedy — O(n log n) |
| Choices interact; subproblems repeat | Dynamic programming — O(n × capacity) |
| Choices interact; no overlap; small n | Backtracking with pruning |
| Need a good answer, not the best | Heuristic or approximation |
Approximation is a legitimate answer
Many optimisation problems are NP-hard, so exact solutions are infeasible at scale. Greedy then returns as an approximation algorithm with a proven bound:
- Set cover — greedy is within a factor of ln n of optimal, and no polynomial algorithm does meaningfully better unless P = NP.
- Bin packing — first-fit decreasing uses at most 11/9 of the optimal number of bins.
- Vertex cover — taking both ends of an uncovered edge is within a factor of 2.
Being able to say "greedy is not optimal here, but it is a 2-approximation and runs in O(n log n), which is the right trade for this scale" is a strong senior-level answer.
Hybrid strategies
Greedy often survives as a component:
- as an initial solution that local search improves;
- as a bound that prunes branches in branch-and-bound;
- as the tiebreaker inside a DP when several transitions are equally good.
The habit to keep
State your strategy, hunt for a counterexample for sixty seconds, and only then commit. If you find one, say so and escalate — noticing that greedy fails is a stronger signal than confidently coding the wrong thing, and it leads directly into the dynamic programming answer the interviewer was waiting for.