Foundations
Greedy
Make the best local choice and commit. Sometimes that's all you need - if you can prove it.
What is greedy?
A greedy algorithm makes the choice that looks best right now, without reconsidering past choices or looking ahead. At each step it picks the locally optimal option and moves on. This works when the greedy choice property holds: a locally optimal choice is always part of a globally optimal solution. When that property holds, greedy produces the global optimum in a single pass.
The key contrast with dynamic programming: DP considers all choices and caches overlapping subproblems. Greedy commits to one choice at each step. If the problem has the greedy choice property, greedy is faster - usually O(n log n) for the initial sort plus O(n) for the scan, versus O(n^2) or O(nk) for DP.
The exchange argument is the standard proof technique for greedy correctness. Assume an optimal solution differs from the greedy solution at some step. Show you can swap the optimal choice for the greedy choice without making the solution worse. If that swap is always safe, the greedy choice is always correct - the optimal solution can be transformed step by step into the greedy solution without losing quality.
Interval scheduling is the canonical greedy domain. Given a set of intervals, select the maximum number of non-overlapping ones. The greedy rule: always pick the interval that ends earliest. Intuitively, the earliest-ending interval leaves the most remaining time for future intervals. The exchange argument confirms it: if an optimal solution skips the earliest-ending interval in favor of a longer one, you can swap in the shorter one without reducing the count.
Core operations
| Pattern | Sort by | Greedy decision | Why it works |
|---|---|---|---|
| Interval scheduling (max non-overlapping) | End time ascending | Take interval if start ≥ last end | Earliest-ending leaves most room for future intervals |
| Interval merging | Start time ascending | Merge if current start ≤ last end | Adjacent intervals must overlap to be merged |
| Min rooms (max concurrent) | Start time, end times separately | Use heap; reuse room if freed up | Max concurrent meetings = min rooms needed |
| Task scheduling (min wait time) | Duration ascending | Always pick shortest remaining task | Minimizes total waiting time (SPTF) |
| Jump game (reachability) | No sort needed | Track farthest reachable index | Farthest reach from any visited position is optimal |
Key patterns
Interval scheduling
Walk the intervals in order of when they finish and grab each one that does not collide with the last one you took.
When to use - you are handed a set of intervals and asked for the most you can pick without any two overlapping: maximum non-overlapping meetings, fewest intervals to remove, most activities you can attend. A brute-force search over every subset is exponential. Greedy works here only because picking the earliest-finishing interval is provably safe - the exchange argument shows swapping it in never lowers the count - so be honest that the trick fails the moment a local pick is not provably globally optimal.
How it works - sort by end time, not start time, then scan once. Keep last_end and accept an interval when its start is at or after last_end, updating last_end to the accepted interval's end. The end-time sort is the whole game: after each accept, the last interval you took finishes as early as possible, which leaves the widest remaining window for everything still ahead. The exchange argument proves it - if an optimal solution skipped the earliest-finishing interval, you could swap that interval in without reducing the count. The sort costs O(n log n) and dominates the O(n) scan.
Example: fit the most non-overlapping meetings. Given 2-25, 7-12, 16-22, sorting by end time lines up 7-12, 16-22, 2-25, so the scan keeps 7-12 (last_end becomes 12) and 16-22 (it starts at 16, no collision). When 2-25 finally comes up, its start of 2 is below last_end of 22, so it is dropped and the count stays 2. Had you sorted by start instead, 2-25 would come first and block both. The visualizer below walks the sorted scan.
Greedy with a running extreme (jump game)
Sweep left to right while carrying one number: the farthest index you could reach from anything you have seen so far.
When to use - the question is "can you reach the end?" or "what is the fewest moves to get there?" and the whole state collapses to a single running maximum. Reach for it when no earlier choice locks you out of a later one, so a left-to-right sweep with one local rule suffices and full dynamic programming is overkill. As always with greedy, this only holds because the local choice - always extend the frontier as far as possible - is provably the global optimum here.
How it works - keep farthest, the best index reachable so far. At each index, first check reachability: if index > farthest, you have hit a gap and can stop. Only then update farthest = max(farthest, index + nums[index]). The order matters - extending the frontier from a position you cannot actually reach would paper over the gap. For minimum jumps, treat each jump's reach as a level boundary: when the scan crosses the current boundary, take one jump and advance the boundary to farthest. This is valid because every index inside a level is equally one jump away, so the only question is how far the level stretches. One pass, O(n).
Example: can you reach the last index?. For [4, 2, 1, 3, 5], index 0 stretches farthest to 4, which already covers the last index, so the walk finishes True at index 1. For [3, 2, 1, 0, 6], the frontier stops at 3 and never grows past it, so at index 4 the check index > farthest fires and the answer is False - the 0 at index 3 strands you there. The visualizer below extends the frontier one index at a time.
index > farthest before updating - if you update farthest first, you might extend the frontier from an unreachable position, masking the gap. Always check reachability of the current index before using it to extend the frontier.When to reach for greedy
- The problem involves selecting a subset of intervals to maximize count or minimize overlap.
- You need the minimum number of resources (rooms, platforms, workers) to handle a set of concurrent tasks.
- The problem has a clear ordering (by end time, deadline, ratio) after which the best local choice is obvious at each step.
- An exchange argument convinces you: swapping any greedy choice for a different choice cannot improve the result.
- DP feels like overkill - the problem has no recombining subproblems, just a single left-to-right sweep.
- The problem asks for the minimum number of operations, jumps, or arrows to cover or reach all targets.
- The question is "can you reach the end?" or "what is the fewest moves?" and the state reduces to a single running maximum.
Done reading? Mark it so it sticks in your dashboard.