貪欲アルゴリズム
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?
Discussion
Sign in to join the discussion