Scheduling
Many scheduling problems can be solved using greedy algorithms. A classic problem is as follows: Given $n$ events with their starting and ending times, find a schedule that includes as many events as possible. It is not possible to select an event partially. For example, consider the following events:
| event | starting time | ending time |
|---|---|---|
| A | 1 | 3 |
| B | 2 | 5 |
| C | 3 | 9 |
| D | 6 | 8 |
In this case the maximum number of events is two. For example, we can select events $B$ and $D$ as follows:
It is possible to invent several greedy algorithms for the problem, but which of them works in every case?
Algorithm 1
The first idea is to select as short events as possible. In the example case this algorithm selects the following events:
However, selecting short events is not always a correct strategy. For example, the algorithm fails in the following case:
If we select the short event, we can only select one event. However, it would be possible to select both long events.
Algorithm 2
Another idea is to always select the next possible event that begins as early as possible. This algorithm selects the following events:
However, we can find a counterexample also for this algorithm. For example, in the following case, the algorithm only selects one event:
If we select the first event, it is not possible to select any other events. However, it would be possible to select the other two events.
Algorithm 3
The third idea is to always select the next possible event that ends as early as possible. This algorithm selects the following events:
It turns out that this algorithm always produces an optimal solution. The reason for this is that it is always an optimal choice to first select an event that ends as early as possible. After this, it is an optimal choice to select the next event using the same strategy, etc., until we cannot select any more events. One way to argue that the algorithm works is to consider what happens if we first select an event that ends later than the event that ends as early as possible. Now, we will have at most an equal number of choices how we can select the next event. Hence, selecting an event that ends later can never yield a better solution, and the greedy algorithm is correct.