14.26 Chapter Summary
Greedy algorithms are among the most elegant techniques in algorithm design.
14.26 Chapter Summary
Greedy algorithms are among the most elegant techniques in algorithm design. They solve complex optimization problems through a sequence of simple decisions:
Choose the best option now.
Commit immediately.
Never reconsider.
At first, this approach seems risky. Most optimization problems involve many interacting choices, and a poor early decision can easily destroy optimality.
Yet certain problems possess hidden structure that makes local decisions surprisingly powerful. When that structure exists, a carefully chosen greedy rule can produce an optimal solution while remaining simpler and faster than alternative approaches.
This chapter explored both the algorithms themselves and, more importantly, the reasoning that makes them correct.
The Core Idea
Every greedy algorithm revolves around a single question:
Can a locally optimal choice be extended into a globally optimal solution?
If the answer is yes, a greedy algorithm may exist.
If the answer is no, other techniques such as dynamic programming, backtracking, branch and bound, or approximation algorithms are usually required.
Understanding this distinction is the foundation of greedy algorithm design.
Greedy Is About Commitment
Unlike dynamic programming:
Explore many possibilities.
Compare solutions later.
Greedy algorithms commit immediately.
Unlike backtracking:
Try a choice.
Undo if necessary.
Greedy algorithms never undo decisions.
Unlike exhaustive search:
Examine every solution.
Greedy algorithms examine only one path.
This commitment is both the strength and weakness of the technique.
When the greedy choice is safe, the algorithm becomes remarkably efficient.
When the greedy choice is unsafe, correctness collapses.
Common Greedy Patterns
Throughout the chapter, several recurring patterns appeared repeatedly.
Earliest Finish Time
Examples:
- Activity selection
- Interval scheduling
Principle:
Free resources as early as possible.
Earliest Deadline
Examples:
- Deadline scheduling
- Real-time systems
Principle:
Handle urgent constraints first.
Highest Density
Examples:
- Fractional knapsack
Principle:
Maximize value per unit resource.
Smallest Frequency
Examples:
- Huffman coding
Principle:
Combine least expensive components first.
Largest Available Resource
Examples:
- Refueling stops
Principle:
Use the strongest available recovery option.
Longest Job Removal
Examples:
- Course scheduling
- Prefix constraints
Principle:
Recover the greatest capacity when overloaded.
Although the applications differ, the underlying reasoning remains remarkably similar.
Data Structures Matter
A greedy algorithm consists of two parts:
- The greedy choice.
- The mechanism used to find that choice efficiently.
Several data structures appeared throughout the chapter.
| Structure | Typical Use |
|---|---|
| Sorted array | Static ordering |
| Min-heap | Smallest candidate |
| Max-heap | Largest candidate |
| Stack | Monotonic frontier |
| Queue | Ordered processing |
| Union-find | Connectivity |
| Frequency table | Counting |
The proof identifies the correct choice.
The data structure makes the choice practical.
Both components are necessary.
Sorting as a Design Tool
Many greedy algorithms begin with:
Sort first.
Examples:
| Problem | Sort Key |
|---|---|
| Activity selection | Finish time |
| Course scheduling | Deadline |
| Fractional knapsack | Density |
| Merge intervals | Start time |
| Rescue boats | Weight |
Sorting reveals structure.
Once elements appear in the correct order, a simple scan often produces the optimal solution.
This is one of the most important design patterns in algorithm engineering.
Priority Queue Greedy
Another recurring pattern was:
Maintain candidates.
Choose best candidate.
Update candidate set.
Examples:
- Huffman coding
- Dijkstra
- Prim
- Refueling stops
- Meeting rooms
- Course scheduling
Priority queues frequently reduce complexity from:
$$ O(n^2) $$
to:
$$ O(n \log n) $$
making them one of the most valuable tools in greedy algorithm design.
String Greedy
Strings introduced additional challenges because future characters matter.
Important techniques included:
- Monotonic stacks
- Lexicographic optimization
- Earliest feasible matching
- Last-occurrence partitioning
- Frequency-based selection
A common theme emerged:
A character can only be removed if the future remains feasible.
This idea parallels the exchange arguments used elsewhere in the chapter.
Graph Greedy
Graph algorithms demonstrated that greedy reasoning extends far beyond simple sorting.
Key examples:
- Kruskal
- Prim
- Dijkstra
These algorithms rely on deeper structural properties:
- Cut properties
- Safe edges
- Monotonicity
- Connectivity invariants
Graph greedy algorithms are often the first place where proofs become substantially more sophisticated than the implementations themselves.
Scheduling as a Natural Greedy Domain
Scheduling problems appeared repeatedly because they naturally reward local decisions that preserve future flexibility.
Recurring scheduling patterns included:
| Objective | Greedy Rule |
|---|---|
| Maximum activities | Earliest finish |
| Feasible schedule | Earliest deadline |
| Minimum completion time | Shortest processing time |
| Maximum profit | Highest profit |
| Capacity recovery | Remove longest job |
Recognizing these patterns often allows new scheduling problems to be solved quickly.
Local vs Global Optimality
One of the most important lessons in the chapter is that:
Locally attractive
≠
Globally optimal
Examples included:
- 0/1 knapsack
- Coin change
- Incorrect interval strategies
- Various counterexamples
A greedy algorithm succeeds only when local improvements align with global objectives.
This alignment is the true subject of greedy proofs.
Counterexamples
Counterexamples serve two purposes:
Reject Bad Rules
Example:
Choose earliest starting interval.
Counterexamples quickly expose flaws.
Improve Design
A failed greedy rule often suggests a better one.
Example:
Earliest start
→
Earliest finish
Many successful greedy algorithms emerged from understanding why simpler rules fail.
Proof Techniques
The chapter repeatedly returned to a small set of proof methods.
Exchange Arguments
Most common.
Transform an optimal solution to include the greedy choice.
Greedy-Choice Property
Show that some optimal solution begins with the greedy choice.
Optimal Substructure
After the greedy choice, the remaining problem has the same form.
Cut Property
Fundamental in minimum spanning trees.
Contradiction
Assume greedy fails and derive impossibility.
Invariants
Show that a key property remains true throughout execution.
Although the algorithms varied widely, these proof techniques appeared again and again.
Complexity Lessons
Greedy algorithms are often efficient because:
- Choices are made once.
- Decisions are never revisited.
- Data structures support fast candidate selection.
Typical complexities:
| Pattern | Complexity |
|---|---|
| Sort + scan | O(n log n) |
| Heap-based | O(n log n) |
| Monotonic stack | O(n) |
| Two pointers | O(n) after sorting |
| Union-find MST | O(E log E) |
Many algorithms that appear quadratic become linear through amortized analysis.
Understanding why is an important skill.
A Practical Workflow
When approaching a new optimization problem:
1. Define objective.
2. Search for ordering.
3. Propose greedy choice.
4. Test examples.
5. Find counterexamples.
6. Attempt exchange argument.
7. Verify optimal substructure.
8. Choose supporting structure.
9. Analyze complexity.
10. Prove correctness.
This workflow mirrors how many classical greedy algorithms were originally discovered.
When Greedy Is Not Enough
Some problems resist greedy solutions.
Examples:
- 0/1 knapsack
- Traveling salesman
- Weighted interval scheduling
- General set cover optimization
- Many NP-hard problems
In these cases:
- Dynamic programming
- Approximation algorithms
- Search techniques
often become necessary.
Recognizing when greedy does not apply is just as important as recognizing when it does.
Greedy Thinking Beyond Algorithms
The ideas developed in this chapter extend beyond traditional algorithm design.
Greedy reasoning appears in:
- Operating systems
- Network routing
- Compression systems
- Cloud scheduling
- Manufacturing planning
- Database optimization
- Distributed systems
Whenever resources are limited and decisions must be made incrementally, greedy ideas often emerge naturally.
The challenge is determining whether those decisions are merely reasonable or provably optimal.
Final Takeaway
Greedy algorithms succeed when a locally optimal decision can be shown to belong to some globally optimal solution. The most important skills are identifying safe choices, constructing counterexamples, applying exchange arguments, maintaining invariants, and selecting data structures that support efficient implementation. Individual algorithms may differ dramatically, but the underlying reasoning remains remarkably consistent. Once you learn to recognize the structural conditions that justify local decisions, greedy algorithms become not a collection of tricks but a systematic approach to optimization.