Activity Selection
Sort by finish times and select maximum non-overlapping tasks scheduling.
Fractional Knapsack
Fill knapsack fractionally using sorted value/weight density ratios.
Job Sequencing
Schedule jobs in free slots before deadlines to maximize revenue yields.
Minimum Platforms
Determine minimum station platform tracks to prevent train scheduling waiting overlaps.
Interval Scheduling
Select the maximum mutually compatible interval segments subset.
Merge Intervals
Sort by start times and merge overlapping ranges greedily.
Huffman Coding
Construct optimal prefix binary trees for data compression schemas.
Coin Greedy
Verify local greedy choice optimality against global optimal changes.
Gas Station
Identify starting station index completing circular path gas checks.
Optimal Merge Pattern
Construct optimal pairwise merges trees using min-priority queues.
Load Balancing
Distribute task loads greedily across bins to minimize peak makespans.
The Greedy Method Paradigm
Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate local benefit. To prove its correctness, it must satisfy:
- Greedy Choice Property: A globally optimal solution can be reached by making locally optimal (greedy) choices.
- Optimal Substructure: An optimal solution to the global problem contains optimal solutions to subproblems.
How to Prove Greedy Correctness
Unlike Dynamic Programming which checks all subproblems, Greedy makes a single irrevocable decision. Proofs of correctness generally use:
- Exchange Arguments: Show that any optimal solution can be converted into the greedy solution without losing quality.
- Greedy Stays Ahead: Show that at each step of the algorithm, greedy is at least as good as any other choices pattern.