Part IV · Fundamental Algorithm Design Paradigms
21. Greedy Algorithms and Exchange Arguments
8 lessons•37 topics•Intermediate
8 of 8 lessons published
21.013 animated
Greedy fundamentals
- Locally optimal decision
- Greedy-choice property
- Optimal substructure
- Greedy vs DP
- Counterexamples
21.022 animated
Correctness proofs
- Exchange argument
- Staying-ahead proof
- Cut property
- Greedy invariant
- Matroid viewpoint introduction
21.036 animated
Interval scheduling
- Activity selection
- Interval merging
- Minimum meeting rooms
- Interval covering
- Minimum arrows
- Non-overlapping intervals
21.045 animated
Resource allocation
- Job sequencing with deadlines
- Fractional knapsack
- Minimum platforms
- Gas station
- Assign cookies
21.054 animated
String and frequency greedy
- Huffman coding
- Reorganize string
- Minimum adjacent operations
- Lexicographic construction
21.064 animated
Greedy with sorting/heaps
- Connect ropes minimum cost
- Merge files optimal pattern
- Scheduling with deadlines
- Max tasks before deadlines
21.074 animated
Graph-related greedy
- Kruskal's MST
- Prim's MST
- Dijkstra's nonnegative weights
- Counterexamples with negative edges
21.084 animated
Coin systems
- Canonical coin systems
- Greedy coin change
- When greedy fails
- Unbounded coin change DP comparison