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

Taught in

References