⚡ Part 4: Greedy Algorithms
Elegant algorithms with no complex recurrences — just one clever observation. Learn when greedy works, how to prove it, and powerful greedy + binary search combos.
📚 2 Chapters · ⏱️ Estimated 1-2 weeks · 🎯 Target: Activity selection, scheduling, binary search + greedy
Part 4: Greedy Algorithms
Estimated time: 1–2 weeks
Greedy algorithms are elegant: no complex recurrences, no state explosions — just one clever observation that makes everything fall into place. The challenge is knowing when greedy works and being able to prove it when it does.
What Topics Are Covered
| Chapter | Topic | The Big Idea |
|---|---|---|
| Chapter 4.1 | Greedy Fundamentals | When greedy works; exchange argument proofs |
| Chapter 4.2 | Greedy in USACO | Real USACO problems solved with greedy |
What You'll Be Able to Solve After This Part
After completing Part 4, you'll be ready to tackle:
-
USACO Bronze:
- Simulation with greedy decisions (process events optimally)
- Simple sorting-based greedy
-
USACO Silver:
- Activity selection (maximum non-overlapping intervals)
- Scheduling problems (EDF, minimize lateness)
- Greedy + binary search on answer
- Huffman-style merge problems (priority queue)
Key Greedy Patterns
| Pattern | Sort By | Application |
|---|---|---|
| Activity selection | End time ↑ | Max non-overlapping intervals |
| Earliest deadline first | Deadline ↑ | Minimize maximum lateness |
| Interval stabbing | End time ↑ | Min points to cover all intervals |
| Interval covering | Start time ↑ | Min intervals to cover a range |
| Fractional knapsack | Value/weight ↓ | Maximize value with capacity |
| Huffman merge | Use min-heap | Minimum cost encoding |
Prerequisites
Before starting Part 4, make sure you can:
- Sort with custom comparators (Chapter 3.3)
-
Use
priority_queue(Chapter 3.1) - Binary search on the answer (Chapter 3.3) — used in Chapter 4.2
The Greedy Mindset
Before coding a greedy solution, ask:
- What's the "obvious best" choice at each step?
- Can I make an exchange argument? If I swap the greedy choice with any other choice, does the solution only get worse (or stay the same)?
- Can I find a counterexample? Try small cases where the greedy might fail.
If you can answer (1) and (2) but not find a counterexample for (3), your greedy is likely correct.
Tips for This Part
- Greedy is the hardest part to "verify." Unlike DP where you just need the right recurrence, greedy requires a correctness argument. Practice sketching exchange argument proofs.
- When greedy fails, DP is usually the fix. The coin change example (Chapter 4.1) shows this perfectly.
- Chapter 4.2 has real USACO problems — work through the code carefully, not just the high-level idea.
- Greedy + binary search (Chapter 4.2) is a powerful combination that appears frequently in Silver. The greedy solves the "check" function, and binary search finds the optimal answer.
💡 Key Insight: Sorting is the engine of most greedy algorithms. The sort criterion embodies the "greedy choice" — choosing the best element first. The exchange argument proves that this criterion is optimal.
🏆 USACO Tip: In USACO Silver, if a problem asks "maximum X subject to constraint Y" or "minimum cost to achieve Z," first try binary search on the answer with a greedy check. This combination solves a surprising fraction of Silver problems.