Greedy Algorithms
Greedy algorithms take the best-looking choice at each step and never reconsider. When that works the code is short and fast, and when it does not the code is short, fast and wrong, with no error to warn you. So the interesting question is never how to implement a greedy algorithm, it is how to know you are allowed to. The answer is an exchange argument, and interviewers in this topic are usually testing whether you look for one.
Where to start, and what comes next
- 01
Interval Scheduling
Interval scheduling, where sorting by finish time is provably correct. The cleanest example of an exchange argument in the topic.
- 02
Jump Game
Jump game, where a running frontier replaces a search. Short, and a good demonstration that greedy is not always about sorting.
- 03
Task Scheduling
Scheduling with cooldowns and deadlines, where the greedy choice is about placement rather than selection.
- 04
Classic Greedy
Gas station, candy and fractional knapsack. Each has a non-obvious argument for why the local choice is safe.
If you only have time for three things
- Sorting by the right key, which is usually the end of an interval rather than the start. Sorting by start is the classic wrong answer.
- The exchange argument: take any optimal solution without your greedy choice and show you can swap it in without making things worse.
- Knowing the standard counterexamples, particularly coin change with 1, 3 and 4 making 6, where greedy gives three coins and two is correct.
Say why the greedy choice is safe, not just what it is. A one-sentence exchange argument turns a guess into a proof sketch, and it is what the question is usually for. If you cannot construct one, say so and use dynamic programming, which is correct everywhere greedy is and in many places it is not.
The idea underneath
Greedy is NOT 'try the obvious thing'. It works only when local optimality guarantees global optimality. Sort first (by end time, deadline, ratio), then pick greedily. If greedy fails, try DP.
Problems that use these patterns
Head to head
Questions people ask
How do I know greedy will work?
Try to prove it by exchange. Assume an optimal solution that differs from your greedy choice, then show you can substitute your choice in without making the result worse. If the substitution breaks something, greedy is unsafe here.
Why sort intervals by end time and not start?
The activity that finishes earliest leaves the most room for everything after it. Sorting by start means a single very long interval can be chosen first and block several shorter ones, and sorting by duration fails on a different family of inputs.
Is Dijkstra a greedy algorithm?
Yes. It settles the nearest unvisited node and never revisits it, which is exactly a greedy commitment. That commitment is also why it breaks on negative edges, where a later route can undercut a node already settled.