Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 18m 45s17 days 22 hours 18 minutes 45 seconds.

Algorithms - Greedy · 5:25

Greedy Algorithms and the Exchange Argument

A greedy algorithm commits to the choice that looks best right now and never undoes it, so it is only correct with a proof. We schedule three jobs [3, 1, 2] on one machine, watch adjacent swaps cut the total finishing time from 13 to 11 to 10, and turn that into the exchange argument: an adjacent swap changes the total by the difference of the two lengths, so shortest-first is optimal and sorting by that key is the algorithm. Then a greedy that fails: coin change with {1, 3, 4} pays 6 as 4+1+1 instead of 3+3, a counterexample a stress test against an exact DP finds instantly.

You will learn

Explain what makes an algorithm greedy (a locally best, irreversible choice) and why it needs a proof
Prove shortest-processing-time first optimal with an adjacent-swap exchange argument
Turn an exchange argument into a comparator (the permutation method) and keep that comparator a strict weak ordering
Break a wrong greedy with a stress test against a brute force, and recognise interacting choices that need DP

Chapters

PreviousStars and Bars NextSort-and-Match Greedy