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
- greedy-choice property — The property of a problem that a globally best solution can always be reached by making the locally best choice at each step.
- greedy algorithm — An algorithm that builds a solution step by step, always taking the choice that looks best right now and never revisiting it.
- interval scheduling — The problem of choosing as many non-overlapping time intervals as possible, such as meetings in one room.
Taught in
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers