貪欲アルゴリズム
What Makes an Algorithm Greedy?
A greedy algorithm builds a solution one step at a time, always picking the option that looks best right now - without reconsidering past choices. No backtracking, no looking ahead.
It works when two properties hold:
- Greedy choice property - a locally optimal choice leads to a globally optimal solution.
- Optimal substructure - the remaining problem after each choice is a smaller instance of the same problem.
Activity Selection - The Classic Example
Given a set of activities with start and end times, select the maximum number of non-overlapping activities.
Greedy strategy: sort by end time, always pick the activity that finishes earliest.
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
Why does this work? Picking the earliest-finishing activity leaves the most room for future activities. No other choice can do better.
Huffman Coding - Concept
Build an optimal prefix-free binary code by repeatedly merging the two lowest-frequency symbols. This is greedy: at each step, merge the cheapest pair. The result is a tree where frequent symbols get short codes.
Jump Game
Given an array where nums[i] is the maximum jump length from index i, determine if you can reach the last index.
Greedy approach: track the farthest index reachable so far. Scan left to right - if you ever fall behind, return false.
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return True
In the Jump Game, what does the greedy variable 'farthest' represent?
Gas Station
Travel a circular route with gas stations. At station i you gain gas[i] fuel and spend cost[i] to reach the next station. Find the starting station that lets you complete the circuit, or return −1.
Greedy insight: if total gas ≥ total cost, a solution exists. Track a running surplus; whenever it drops below zero, the answer must start after that point.
Task Scheduler
Schedule tasks with a cooldown of n between identical tasks. Greedy: always pick the most frequent remaining task. The answer depends on the maximum frequency and how many tasks share it.
Tasks: A A A B B C, cooldown = 2
Schedule: A B C A B _ A
Total = 7
Fractional Knapsack vs 0/1 Knapsack
Fractional knapsack: you can take fractions of items. Greedy works - sort by value-per-weight, take the best ratio first.
0/1 knapsack: items are all-or-nothing. Greedy fails here because skipping a heavy-but-valuable item might be worse than taking two lighter ones. This requires dynamic programming.
Items: (weight=3, value=4), (weight=2, value=3), (weight=2, value=3)
Capacity: 4
Greedy (best ratio first): takes item 1 (w=3, v=4) → 1 remaining → can't fit rest → value = 4
Optimal: takes items 2+3 (w=4, v=6) → value = 6 ✗ Greedy fails!
Why does the greedy approach fail for the 0/1 knapsack problem?
When Does Greedy Work?
✅ Works when you can prove the greedy choice property:
- Interval scheduling, Huffman coding, minimum spanning trees, Dijkstra's algorithm, coin change with standard denominations
❌ Fails when local optima don't compose into global optima:
- 0/1 knapsack, longest path in general graphs, travelling salesman
Proving Greedy Correctness - Exchange Argument
The standard technique: assume an optimal solution that doesn't use the greedy choice. Show you can exchange one of its choices for the greedy choice without making the solution worse. This proves greedy is at least as good.
What is the 'exchange argument' used for?
Greedy vs Dynamic Programming
| Aspect | Greedy | Dynamic Programming | |--------|--------|---------------------| | Choices | One best choice per step | Explore all sub-problems | | Revisits past? | Never | Yes - stores sub-results | | Speed | Usually faster | Depends on state space | | Correctness | Only if provable | Always (if formulated right) |
When in doubt, start greedy - if you can't prove it works, switch to DP.
📚 Further Reading
- NeetCode - Greedy playlist - curated greedy problems with explanations
- Tech Interview Handbook - Greedy - when to use greedy and common patterns
- CP-Algorithms - Greedy algorithms - deeper theory and proofs