AdvancedGreedy & Intervals
When is greedy safe?
Greedy is right when taking the locally best move can never hurt later. Try to argue that, or find a counterexample, before coding.
The idea
A greedy algorithm commits to the best-looking choice now and never reconsiders. It's fast and simple, but only correct when an exchange argument holds: any optimal answer can be changed to include your choice without getting worse.
If you can't argue it, test small inputs. One counterexample means you need DP or search instead.
Worked example
Jump Game: [2, 3, 1, 1, 4]
- Track the farthest index reachable so far: 0 + 2 = 2, then 1 + 3 = 4 → can reach the end.
- Greedy works: reaching farther is never worse than reaching less far.
- Contrast coin change with coins [1, 3, 4] for 6: greedy takes 4 + 1 + 1 (3 coins) but 3 + 3 is 2. Greedy fails there.
In code (Python)
def can_jump(nums):
farthest = 0
for i, step in enumerate(nums):
if i > farthest:
return False # this index can't be reached
farthest = max(farthest, i + step)
return TrueO(n) time, O(1) space.
How to spot it
- Scheduling, intervals, jumps, “minimum number of …” where a simple rule might suffice.
Common mistakes
- Assuming greedy works because it passed the examples.
- Using greedy for coin change with arbitrary coins.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →