aloalgoWhen Greedy Works
Greedy doesn't always give the optimal solution. The key question: does choosing the best option now lead to the best overall solution? This page helps you recognize when greedy is the right approach.The Greedy Choice Property
Greedy works when the problem has the greedy choice property: a globally optimal solution can be reached by making locally optimal choices. This means choosing the best option now never prevents finding the best overall solution.Signs That Greedy Works
- Optimal substructure: Optimal solution contains optimal solutions to subproblems.
- No "undo" needed: Once you make a choice, you never need to reconsider it.
- Sorting helps: Many greedy problems become clear after sorting by some criteria.
- Interval/scheduling patterns: Problems involving time ranges often work with greedy.
- Exchange argument possible: You can prove swapping any choice with the greedy choice doesn't hurt.
Classic Greedy Problems
Activity Selection
Select maximum non-overlapping activities. Greedy works: pick the one that ends earliest.Jump Game
Determine if you can reach the end. Greedy works: track the farthest position reachable.Gas Station
Find starting station to complete a circuit. Greedy works: if total gas >= total cost, solution exists.Assign Cookies
Maximize children satisfied with cookies. Greedy works: give smallest sufficient cookie to each child.When Greedy Fails
Greedy fails when a locally optimal choice prevents finding the globally optimal solution. Always test with counterexamples!More Greedy Failures
Proving Greedy Correctness
Two common proof techniques for showing greedy works:1. Greedy Stays Ahead
Show that after each step, the greedy solution is at least as good as any other solution at that point.2. Exchange Argument
Show you can transform any optimal solution into the greedy solution without making it worse.Decision Framework
- Identify the greedy choice: What's the "best" option at each step?
- Check for counterexamples: Try small inputs where greedy might fail.
- Verify the properties: Does it have optimal substructure? No undo needed?
- If greedy fails: Switch to DP or other approaches.
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.