Why greedy works
Overview
A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. It works when this local, short-term optimization inevitably leads to a global, long-term optimum.
When applicable, greedy algorithms are exceptionally fast and simple to implement, usually avoiding complex state management or recursion.
Where used: Minimum Spanning Trees, Shortest path finding, Data compression, Job sequencing
Why learn this
- You need to know when you can safely use a fast greedy approach instead of an exhaustive search.
- Understanding the underlying proofs (like the exchange argument) prevents you from guessing on algorithm design.
- It forms the theoretical foundation for major graph algorithms you have already seen, like Kruskal's algorithm.
Common mistakes
- Assuming greedy always works: The most common trap is inventing a greedy heuristic that seems intuitive but fails on edge cases. A greedy choice must be rigorously provable.
- Confusing optimal substructure with greedy-choice property: Dynamic programming also uses optimal substructure. Greedy requires the extra 'greedy-choice' property: the single best immediate choice is always part of the global optimum, meaning you never need to backtrack.
Recall questions
- What two properties must a problem have for a greedy algorithm to yield an optimal solution?
- What is the exchange argument?
Understanding checks
How does the exchange argument justify the greedy choice in interval scheduling?
If an optimal schedule doesn't pick the interval ending earliest, you can swap that early-ending interval in place of the first interval in the optimal schedule. Because the greedy choice ends earlier, the swap frees up more room and cannot conflict with the rest of the schedule.
This proves that picking the earliest ending interval never forecloses a better outcome.
If a problem has optimal substructure but lacks the greedy-choice property, can you use a greedy algorithm?
No, you usually need dynamic programming instead.
Without the greedy-choice property, a locally optimal choice might lead you down a suboptimal path, requiring you to explore multiple branches.
Practice tasks
Mental exchange argument
Think of Kruskal's algorithm. If an optimal spanning tree does not include the cheapest edge in the graph, how could you use an exchange argument to prove it should?
Continue learning
Previous: Minimum Spanning Tree (Kruskal)
Next: Why greedy fails
Next: Interval scheduling