Greedy

Back to Index

Use when: locally optimal choices lead to globally optimal solution. No need to explore all combinations.

Signal words: maximum, minimum, schedule, assign, jump game, interval coverage.

Core Idea

At each step, make the choice that looks best right now and never reconsider.

How to verify greedy is correct: prove that swapping any two adjacent choices in a greedy solution doesn’t improve the result (exchange argument).

Common Greedy Patterns

Interval Scheduling (maximize non-overlapping intervals)

Sort by end time, greedily pick intervals that don’t conflict.

intervals.sort(key=lambda x: x[1])
end = float('-inf')
count = 0
for start, finish in intervals:
    if start >= end:
        count += 1
        end = finish

Jump Game

Track the farthest reachable index.

max_reach = 0
for i, jump in enumerate(nums):
    if i > max_reach:
        return False
    max_reach = max(max_reach, i + jump)
return True

Key Question

Can I prove that the greedy choice is safe? If not, consider DP.

---

Problems Using This Pattern