Greedy is not "pick what looks best" unless you can explain why that local choice never blocks the global optimum. The proof is usually an exchange argument or an invariant.
Greedy Patterns
| Pattern | Invariant | Lesson |
|---|---|---|
| Farthest reach | If index is beyond reach, all future paths fail | Jump Game |
| Reset start | Negative local tank invalidates the whole candidate range | Gas Station |
| Earliest end | Finishing earlier leaves more future room | Non-overlapping Intervals |
| Last boundary | A partition must include every last occurrence inside it | Partition Labels |
Greedy Checklist
- Define the local choice.
- Show what the choice preserves.
- Explain why delaying or changing the choice cannot improve the result.
FAQs
How do I know greedy is safe?
You need an invariant or exchange argument. If you cannot state one, try DP or backtracking first.
Are interval problems always greedy?
No, but many become greedy after sorting by end time or start time depending on the target.