Question

Show that a greedy algorithm that schedules talks in a lecture hall, as described in Example 7, by selecting at each step the talk that overlaps the fewest other talks, does not always produce an optimal schedule.

Short answer

It is proved that the greedy algorithm that schedules talks in a lecture hall does not always produce an optimal schedule.

Step-by-step solution

Step 1:

In order to show that this algorithm does not always give an output schedule, then we construct a counter example.

So, let us consider three talks:

Talk 1 starts at 8 am and ends at 9.15 am

Talk 2 starts at 9 am and ends at 10am

Talk 3 starts at 9.45 am and ends at 11am .

Step 2:

So, now we will select Talk 2 since it is shortest.

And, as once Talk 2 is selected then it is not possible to select Talk 1 , as it is not compatible.

Therefore, it is proved that the greedy algorithm that schedules talks in a lecture hall does not always produce an optimal schedule.