Greedy algorithms make locally optimal choices at each step. Key is proving that local optimal leads to global optimal.
Time
Usually O(n log n) due to sorting
Space
O(1) to O(n)
Problems
4 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Jump Game | Medium | Amazon Microsoft Google |
| 2 | Non-overlapping Intervals | Medium | Google Amazon Meta |
| 3 | Gas Station | Medium | Amazon Google Goldman Sachs |
| 4 | Task Scheduler | Medium | Meta Amazon Google |
Greedy works when: (1) Greedy choice property + (2) Optimal substructure
Sort by end time for interval problems
If greedy doesn't work, try DP
Proving greedy correctness: show that swapping any non-greedy choice doesn't improve the result
