interval scheduling
The problem of choosing as many non-overlapping time intervals as possible, such as meetings in one room.
In more detail
The greedy rule is to sort by finish time and repeatedly take the next interval that starts after the last one chosen ends. Finishing earliest leaves the most room for the rest, which an exchange argument turns into a proof. It runs in O(n log n) because of the sort.
Related terms
- greedy algorithm — An algorithm that builds a solution step by step, always taking the choice that looks best right now and never revisiting it.
- 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.
Taught in
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers