Skip to interview prep
Apexed

345. What is an exchange argument, and how do you use it to prove a greedy algorithm correct?

HardGreedy algorithms

Technical
Show model answer

Take any optimal solution O that differs from the greedy solution G. Find the first place they disagree and show you can modify O to agree with G there (swap two adjacent jobs, replace an item, move an interval) without making O worse and without breaking feasibility. Repeating the exchange transforms O into G, so G is also optimal.

For example, in shortest-job-first, any schedule with a longer job directly before a shorter one can swap them and lower the total waiting time, so an optimal schedule has no such inversion and must be sorted. The companion technique is 'greedy stays ahead', where you show by induction that after each step the greedy's partial solution is at least as good as any other's. If you cannot construct the exchange, look for a counterexample: the greedy is probably wrong.

What interviewers listen for

  • Transform an optimal solution step by step into the greedy one
  • Each exchange keeps feasibility and does not worsen cost
What is an exchange argument, and how do you use it to prove a greedy algorithm correct — Data structures & algorithms interview question — Apexed