When Greedy Works

A greedy algorithm builds a solution step by step, making a locally optimal choice at each step. It is correct only when that leads to a globally optimal solution. Two properties guarantee this.

Optimal Substructure

The optimal solution to the problem contains optimal solutions to its subproblems.

Example: In the “activity selection” (max non-overlapping intervals), an optimal set that includes one interval I is “I plus an optimal set of intervals that don’t overlap I” — so the subproblem (intervals after I’s end) has the same structure.

Greedy Choice Property

A globally optimal solution can be reached by making a locally optimal choice (and then solving the remaining subproblem).

Example: In activity selection, choosing the interval that ends earliest (among those that don’t overlap already chosen ones) is a valid greedy choice and leads to a global optimum.

When Greedy Fails

• 0/1 Knapsack: Greedy by value/weight ratio can fail; you need DP.
• Shortest path with negative edges: Greedy (Dijkstra) fails; use Bellman–Ford.
• Job scheduling with deadlines and profits: Some variants need DP or other techniques.

If the problem does not have a clear “greedy choice” that stays optimal, try DP or search.

How to Argue Correctness

1. Greedy choice: Show that there exists an optimal solution that includes your first greedy choice.
2. Subproblem: After making that choice, the remaining problem is a smaller instance of the same type.
3. Induction: Combine 1 and 2 to conclude the greedy algorithm is correct.

Summary

Greedy is correct when the problem has optimal substructure and a greedy choice property. When in doubt, try to find a counterexample (small input where greedy gives a worse answer than the optimum); if you can’t, try to prove the two properties above.