exchange argument

A proof technique for greedy algorithms: show that any optimal solution can be changed, one swap at a time, to include the greedy choice without getting worse.

In more detail

For interval scheduling, swap the first interval of any optimal schedule for the one that finishes earliest; nothing else is disturbed, so the greedy choice is safe. Repeating the argument step by step shows the whole greedy solution is optimal.

Related terms

Taught in

References