Greedy: Take the Best Move Now

A greedy algorithm builds its answer one decision at a time. At each step it takes the move that looks best right now and never goes back to change it.

That makes greedy code short and fast: typically sort once, then one pass, so O(n log n) time and O(1) extra space. Compare that with backtracking (try everything) or DP (remember every sub-answer).

The catch: greedy is only correct when the problem has the greedy choice property. Taking the locally best move must never rule out a globally best answer.

How do you know greedy is safe? The exchange argument. Take any optimal answer that does not make the greedy choice. Swap one of its choices for the greedy one and show the answer gets no worse. Then some optimal answer agrees with greedy, and you can repeat the argument for the next step.

Example: you have budget hours and a list of task durations. Finish as many tasks as possible. Greedy: do the shortest tasks first.

Why it's safe: suppose a best plan does a long task L but skips a shorter task S. Swap L for S: same number of tasks, and you spend less time. So "shortest first" is never worse.

When greedy fails. Change the coins to [1, 3, 4] and make 6. Greedy grabs 4, then 1, then 1: three coins. But 3 + 3 uses only two.

Taking the 4 looked best but made the rest of the problem worse. No exchange argument exists here, so you need dynamic programming, which tries every last coin and remembers the best answer for each smaller amount.