Greedy Algorithms
Greedy strategies make the locally optimal choice at each step, leading to a globally optimal solution — when applicable.
Core Concepts
The greedy paradigm works when a problem has the greedy-choice property and optimal substructure. Common interview patterns include:
- Interval Scheduling: Sort by end time, greedily pick non-overlapping intervals.
- Activity Selection: Always select the activity that finishes earliest.
- Jump Game: Track the maximum reachable index at each step.
- Huffman Coding: Use a min-heap to build optimal prefix codes.
- Task Scheduling: Sort by deadline or profit to maximize throughput.
Cheatsheet Formulas
- Interval overlap check: Two intervals [a,b] and [c,d] overlap if
a <= d && c <= b - Merge intervals: Sort by start. Merge if
curr.start <= prev.end. Update end tomax(prev.end, curr.end). - Jump Game (reach):
maxReach = max(maxReach, i + nums[i])for each index i. - When greedy fails: If subproblems are interdependent → use DP instead.
- Greedy vs DP: Greedy = one pass, irreversible decisions. DP = explores all sub-states.