What Problem Does It Solve?
A Greedy algorithm makes the locally optimal choice at each step, betting that a sequence of locally best decisions will produce the globally best result. Think of a hiker choosing the steepest uphill path at every fork — sometimes this reaches the summit fastest, but sometimes it leads to a local peak with no way forward.
The challenge with Greedy is knowing when it is safe to use. It works when the problem has the greedy choice property: a locally optimal choice never forecloses a better global solution.
When Greedy Works: Interval Scheduling
Problem: You have meetings [[0,30],[5,10],[15,20]]. Attend as many as possible without overlap.
Greedy strategy: Always pick the meeting that ends earliest. This is mathematically proven to be optimal — by finishing early, you leave the maximum remaining time for future meetings.
Sorted by end time: [[5,10], [15,20], [0,30]]
Step 1: Take [5,10]. Last end = 10.
Step 2: [15,20] starts at 15 >= 10. Take it. Last end = 20.
Step 3: [0,30] starts at 0 < 20. Skip.
Result: 2 meetings attended.
When Greedy Fails: Coin Change
Problem: Make 6 cents using coins [4¢, 3¢, 1¢].
- Greedy: Take 4¢ (largest). Remaining: 2¢. Take 1¢, 1¢. Total: 3 coins.
- Optimal: Take 3¢, 3¢. Total: 2 coins.
Greedy failed because taking the largest coin blocked a better combination. This problem requires Dynamic Programming instead.
The Diagnostic Question
Before applying Greedy, ask: "Can a locally optimal choice ever prevent a better global outcome?" If yes, use DP. If no (and you can prove it, even informally), Greedy is safe and much faster — typically $O(N \log N)$ due to sorting, versus $O(N \cdot \text{target})$ for DP.