Topic 15 of 20
Make the locally best choice, and learn to prove it is globally optimal.
A greedy algorithm builds a solution step by step, always taking the choice that looks best right now, and never reconsiders. When it works, it is usually the simplest and fastest solution, often a sort followed by a single pass. The catch is that it only works when you can argue that the local choice never hurts the final answer.
The standard proof tool is the exchange argument: take any optimal solution that differs from the greedy one, swap in the greedy choice, and show it is no worse. In an interview you do not need a formal proof, but you should be able to explain why the greedy choice is safe. If you cannot, try a small counter-example, and if the greedy choice fails, the problem probably needs dynamic programming.
Common shapes include sorting by one key then scanning (assigning cookies, two-city scheduling), tracking the furthest reachable point (Jump Game), Kadane's running maximum subarray, and two-pass greedy where you satisfy constraints from the left and then from the right (Candy).
Match the smallest sufficient cookie; the simplest exchange argument.
Prefer giving larger bills as change.
Fractional-knapsack style: best value first.
Place whenever it is legal; a greedy that is easy to justify.
Kadane's algorithm; among the most-asked problems ever.
Sum every positive difference.
Track the furthest reachable index.
Greedy BFS levels for the minimum number of jumps.
Reset the start when the running tank goes negative.
Ignore bad triplets and combine the rest.
Extend each partition to the last occurrence; asked often at Amazon.
Track the range of possible open counts.
A custom comparator (a+b vs b+a).
Sort tall-first, then insert by index.
Sorting by cost difference is the exchange argument in action.
Retroactively refuel at the best station passed.