Greedy Algorithms and Problem-Solving Patterns
Greedy algorithms commit to the locally best choice at each step. They are fast and simple, but only correct when you can prove the greedy choice is safe; pattern recognition tells you which technique a problem calls for.
Key points
- 1
Prove greedy correct with an exchange argument: show any optimal solution can be changed to include the greedy choice without getting worse.
- 2
Interval problems: sort by end time for maximum non-overlapping (activity selection, arrows); sort by start with a min-heap of ends for minimum rooms.
- 3
Fractional knapsack is greedy by value density; 0/1 knapsack and arbitrary coin change are not, and need dynamic programming.
- 4
Read the constraints first: n ≤ 10 allows exponential search, n ≤ 10⁵ needs O(n log n), n ≤ 10⁹ needs O(log n) or math.
- 5
Bit tricks:
n & (n - 1)clears the lowest set bit,x & -xisolates it, XOR cancels pairs, and masks enumerate subsets. - 6
Math helpers: Euclid's gcd is O(log n), the sieve is O(n log log n), and binary exponentiation is O(log e) with a mod at each step.
- 7
Map problem statements to patterns: sorted pairs → two pointers, "longest substring" → sliding window, cycles → fast/slow, running median → two heaps, dependencies → topological sort.
Common traps
Earliest start or shortest duration first look plausible for interval scheduling but have small counterexamples; earliest finish is the proven rule.
Largest-coin-first only works for canonical coin systems like {1, 5, 10, 25}; {1, 3, 4} fails at 6.
Sorting numbers as strings in reverse order isn't the "largest number" order; compare a + b with b + a.
Read the source
Test yourself on Greedy Algorithms and Problem-Solving Patterns
Ten questions, with the answer and explanation after each one.