14.22 Greedy Algorithm Design Checklist
Throughout this chapter, we have studied a wide variety of greedy algorithms: - Interval scheduling - Activity selection - Huffman coding
14.22 Greedy Algorithm Design Checklist
Throughout this chapter, we have studied a wide variety of greedy algorithms:
- Interval scheduling
- Activity selection
- Huffman coding
- Fractional knapsack
- Job sequencing
- Minimum refueling stops
- Course scheduling
- Graph optimization
- String optimization
- Resource allocation
At first glance, these algorithms appear unrelated. They operate on different data structures, optimize different objectives, and use different proof techniques.
Yet successful greedy algorithms are usually discovered through the same design process.
This recipe provides a practical checklist for designing and validating greedy algorithms. Rather than memorizing individual solutions, you can use this framework when encountering a new optimization problem.
The Central Question
Every greedy algorithm begins with the same idea:
Can a locally optimal choice be extended into a globally optimal solution?
If the answer is yes, greedy methods may apply.
If the answer is no, consider:
- Dynamic programming
- Divide and conquer
- Branch and bound
- Backtracking
- Approximation algorithms
The remainder of the checklist helps determine which case you are facing.
Step 1: Identify the Objective
Before designing any algorithm, define the objective precisely.
Examples:
| Problem | Objective |
|---|---|
| Interval scheduling | Maximize selected intervals |
| Fractional knapsack | Maximize value |
| Huffman coding | Minimize encoded size |
| MST | Minimize total edge weight |
| Refueling stops | Minimize stops |
| Course scheduling | Maximize accepted courses |
Many incorrect greedy algorithms optimize the wrong objective.
For example:
Shortest interval
sounds attractive.
But interval scheduling cares about:
Maximum future capacity
which is captured by finish time, not duration.
Always identify the true objective first.
Step 2: Look for a Natural Ordering
Many greedy algorithms emerge after sorting.
Ask:
Can candidates be ordered meaningfully?
Common orderings:
| Ordering | Examples |
|---|---|
| Finish time | Interval scheduling |
| Deadline | Course scheduling |
| Profit | Job sequencing |
| Density | Fractional knapsack |
| Weight | Rescue boats |
| Frequency | Huffman coding |
A useful ordering often reveals the greedy choice.
If no meaningful ordering exists, greedy design becomes harder.
Step 3: Search for the Safest Choice
Ask:
Which choice seems least likely to hurt future opportunities?
Examples:
| Problem | Safe Choice |
|---|---|
| Interval scheduling | Earliest finish |
| Refueling | Largest available fuel |
| MST | Lightest safe edge |
| Huffman | Smallest frequencies |
| Scheduling | Earliest deadline |
Notice a recurring theme:
Preserve future flexibility.
Many greedy algorithms succeed because they avoid restricting future decisions unnecessarily.
Step 4: Test Small Examples
Before attempting a proof:
Create examples.
Example:
3 items
4 jobs
5 intervals
Run the proposed greedy rule manually.
Questions:
- Does it produce the expected answer?
- Does it make suspicious choices?
- Are ties handled correctly?
This step often reveals obvious flaws.
Step 5: Hunt for Counterexamples
Now actively try to break the algorithm.
Ask:
Can one attractive choice
block several better choices?
Common counterexample patterns:
Trap Item
One large item blocks many smaller valuable items.
Bad Remainder
The greedy choice leaves a difficult leftover.
Boundary Blocker
One choice overlaps multiple compatible choices.
Delayed Benefit
A weaker immediate choice creates better future opportunities.
If a small counterexample exists, greedy correctness is unlikely.
Step 6: Attempt an Exchange Argument
This is often the decisive step.
Suppose:
G
is the greedy choice.
Suppose:
O
is an optimal solution.
Can you replace part of:
O
with:
G
without reducing quality?
If yes:
Greedy choice is safe.
If not:
Greedy rule may be wrong.
Most successful greedy algorithms survive this test.
Example
Interval scheduling:
Replace first optimal interval
with earliest finishing interval
Still feasible.
Therefore:
Greedy choice is safe.
The proof begins to emerge naturally.
Step 7: Verify Optimal Substructure
After making the greedy choice:
Ask:
Does the remaining problem look like the original problem?
Examples:
Huffman Coding
Merge smallest frequencies.
Remaining problem:
Smaller Huffman problem
Interval Scheduling
Choose earliest finish.
Remaining intervals:
Smaller interval scheduling problem
Fractional Knapsack
Consume highest density.
Remaining capacity:
Smaller knapsack problem
If the structure changes fundamentally, greedy reasoning often breaks.
Step 8: Identify the Dominant Operation
Once correctness seems plausible:
Determine the key operation.
Examples:
| Operation | Structure |
|---|---|
| Smallest element | Min-heap |
| Largest element | Max-heap |
| Connectivity | Union-find |
| Ordered lookup | Tree |
| Frontier maintenance | Stack |
| Static ordering | Sort |
The data structure should support the greedy choice efficiently.
Step 9: Analyze Complexity
Ask:
How Many Times Is Each Item Processed?
Many algorithms are linear because each element is touched once.
Is Sorting Required?
Sorting often dominates:
O(n log n)
Are Heap Operations Used?
Each operation:
O(log n)
Is Amortized Analysis Needed?
Stacks and two pointers frequently require amortized reasoning.
Do not rely on intuition.
Count operations explicitly.
Step 10: State the Invariant
Many proofs become easier once the algorithm maintains a clear invariant.
Examples:
Interval Scheduling
Selected intervals remain compatible.
Dijkstra
Chosen distances are final.
Course Scheduling
Accepted jobs form the best feasible schedule so far.
Huffman
Merged nodes correspond to optimal subtrees.
A strong invariant often clarifies both correctness and implementation.
Step 11: Compare Against Known Patterns
Many new problems are variations of existing ones.
Ask:
Does It Look Like Scheduling?
Consider:
- Earliest finish
- Earliest deadline
- Highest profit
Does It Look Like Resource Allocation?
Consider:
- Density
- Capacity
- Matching
Does It Look Like Graph Optimization?
Consider:
- Safe edges
- Cuts
- Connectivity
Does It Look Like String Optimization?
Consider:
- Monotonic stacks
- Lexicographic choices
- Frequency tracking
Pattern recognition accelerates design dramatically.
Step 12: Distinguish Exactness from Heuristics
Not every useful greedy algorithm is optimal.
Ask:
Do I have a proof?
If yes:
Exact greedy algorithm
If no:
Greedy heuristic
This distinction matters.
Many production systems use greedy heuristics because they are fast and effective.
That does not automatically make them optimal.
Common Warning Signs
Greedy algorithms often fail when:
Choices Are Highly Interdependent
One decision changes the value of many others.
Resources Are Indivisible
Fractional reasoning no longer works.
Future Constraints Dominate
Current decisions hide future costs.
No Exchange Argument Exists
The proof stalls immediately.
Small Counterexamples Appear Easily
Usually a strong signal that the rule is incorrect.
The Complete Greedy Workflow
When approaching a new problem:
1. Define objective.
2. Look for ordering.
3. Identify safe choice.
4. Test examples.
5. Search for counterexamples.
6. Attempt exchange argument.
7. Verify optimal substructure.
8. Choose data structure.
9. Analyze complexity.
10. State invariant.
11. Compare known patterns.
12. Prove correctness.
This process mirrors how many classical greedy algorithms were originally discovered.
A Case Study
Suppose you encounter:
Select the maximum number of compatible meetings.
Apply the checklist.
Objective
Maximum meetings.
Ordering
Finish times.
Safe Choice
Earliest finish.
Counterexamples
Start-time ordering fails.
Exchange Argument
Replace first interval in optimal schedule.
Optimal Substructure
Remaining intervals form smaller problem.
Data Structure
Sorted array.
Complexity
O(n log n)
The solution emerges systematically.
Beyond This Chapter
The techniques introduced here extend well beyond classical greedy algorithms.
The same reasoning appears in:
- Network routing
- Operating systems
- Compression systems
- Resource schedulers
- Distributed systems
- Approximation algorithms
Greedy thinking is ultimately about identifying decisions that can be committed early without sacrificing optimality later.
That idea recurs throughout computer science.
Takeaway
Successful greedy algorithms are rarely discovered by intuition alone. They emerge through a structured process: define the objective, identify a meaningful ordering, search for a safe local choice, challenge it with counterexamples, and validate it through exchange arguments and optimal substructure. Once correctness is established, appropriate data structures and complexity analysis complete the design. The most important skill is not memorizing individual algorithms but learning how to evaluate whether a local decision can safely participate in a global optimum. That skill forms the foundation of greedy algorithm design.