Interval scheduling: Difference between revisions

Revision as of 12:05, 13 April 2023

Revision as of 00:19, 14 July 2023

Line 31:

# Repeat until the set of candidate intervals is empty.

Whenever we select an interval at step 1, we may have to remove many intervals in step 2. However, all these intervals necessarily cross the finishing time of ''x'', and thus they all cross each other (see figure). Hence, at most 1 of these intervals can be in the optimal solution. Hence, for every interval in the optimal solution, there is an interval in the greedy solution. This proves that the greedy algorithm indeed finds an optimal solution.

A more formal explanation is given by a [[Charging argument]].