CodeWithYash

Intermediate · Module 16 · Lesson 2

Exchange arguments

Prove an optimal solution can use the greedy choice.

15–25 min readLesson 90 of 123

Lesson 90 of 123

1d streak

Theory lesson · Step-by-step

Understand Exchange arguments

Prove an optimal solution can use the greedy choice.

Worked approach

Trace the reasoning step by step

  1. 1State the candidate ordering and local choice made by Exchange arguments.
  2. 2Identify the feasibility condition maintained by the partial solution.
  3. 3Use an exchange or stays-ahead argument to justify the choice.
  4. 4Commit the choice and remove candidates it makes impossible.
  5. 5Search for a counterexample before trusting the greedy rule.

Concrete example

Justify choosing the earliest-finishing first interval.

  1. 1Take an optimal schedule whose first interval differs.
  2. 2Swap its first interval with the earlier-finishing greedy one.

The remainder still fits, so an optimum containing the greedy choice exists.

What must remain true (Loop Invariant)

After every choice in Exchange arguments, the partial solution can still be extended to an optimum under the proved exchange or stays-ahead argument.

Cost Model

Complexity & Trade-offs

Proof technique
Matches chosen algorithm
Matches chosen algorithm
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Scheduling, reachability, coding, matching resources, and minimum-cost growth.
  • Problems with an exchange proof or matroid-like safe choices.
  • Online decisions that maintain a best frontier.

Common mistakes

  • Choosing a plausible local optimum without a proof.
  • Using the wrong sorting key.
  • Applying greedy reasoning when choices interact through future state.

Practice prompts

  • Reproduce the worked Exchange arguments example without looking at the trace.
  • Change one input condition and explain whether the Exchange arguments invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.