Course contentsShow
← Computer Science
Lesson 906 of 2,87221. Greedy AlgorithmsFree lesson

Proof by Exchange Argument

Master the exchange argument technique: transforming any optimal solution into the greedy solution.

Proof by Exchange Argument

You'll learn: How to prove a greedy algorithm is correct by showing you can swap any "wrong" choice in an optimal solution with your greedy choice without making things worse.

The Core Idea

An exchange argument proves your greedy algorithm works by taking any optimal solution and gradually transforming it into the greedy solution through a series of "exchanges" (swaps). If each exchange maintains or improves optimality, then the greedy solution must also be optimal.

Think of it like this: Imagine you have two ways to pack boxes for shipping—yours (greedy) and someone else's (allegedly optimal). You prove yours is just as good by swapping items one at a time from their boxes into yours, showing that after each swap, the packing is still at least as efficient.

How It Works

  1. Assume there exists an optimal solution that differs from your greedy solution
  2. Find the first position where they differ
  3. Exchange the optimal solution's choice with the greedy choice at that position
  4. Show this exchange doesn't worsen the solution (maintains optimality)
  5. Repeat until the optimal solution has been transformed into the greedy solution
  6. Conclude the greedy solution must be optimal

Example Structure

For activity selection: If an optimal schedule chooses activity B first but greedy chooses A (which finishes earliest), you show swapping B for A still leaves room for all remaining activities. Since you can always make this swap, greedy must produce an optimal result.

The power is in showing that whatever optimal solution exists, you can morph it into yours without losing optimality.

Key Takeaway: Exchange arguments prove greedy correctness by demonstrating any optimal solution can be step-by-step converted into the greedy solution while preserving optimality.