Q74: Interval Scheduling: Another greedy approach

This question is in continuation of previous question of interval scheduling. Please visit Q7 & Q8 before attempting this question.

Question #74: In another greedy approach, consider the following rule for selecting requests to produce optimal set in interval scheduling problem:

For all requests, find the number of other requests which conflict with it. Then, choose the request with least number of conflicts. Then, eliminate the conflicting requests, and again from the remaining requests, choose the one with least number of conflicts & so on.

Options:

1. The above algorithm produces optimal set always as it is able to select maximum requests since requests with more conflicts can be avoided.
2. This algorithm only fails when all requests conflict with equal number of other requests, but such an example cannot be constructed.
3. This algorithm may not produce optimal set in every case, and counter examples can be constructed.
4. This algorithm doesn’t work as greedy algorithms are unsuccessful in solving problems like this.

Solution: Below is the counter example of the above proposed algorithm:

Here 4 is the optimal number of requests that can be scheduled, but they have maximum conflicts. Hence, the correct answer is 3rd one.