Q8: Interval Scheduling: An alternative approach

Posted on by bytesoftheday

This question is in continuation of previous question of interval scheduling. Please visit Question #7 before attempting this question.

Question #8: Consider a different greedy approach to solve the same problem of finding a subset of maximum size of non-overlapping intervals. This greedy algorithm selects shorter requests first and adds it to the solution if it doesn’t overlap with the existing jobs. The algorithm finally stops until we reach the highest interval job. Which of the following option is correct?

Options:

  1. This algorithm produces optimal set as more number of shorter requests can be covered in a given time as compared to longer ones.
  2. This algorithm will produce optimal set only if a good mix of shorter and longer requests exists.
  3. This algorithm doesn’t produce optimal set in cases when all requests have same size.
  4. We can design some counter examples to prove that this algorithm doesn’t work in all cases, even if requests have varying size.

Solution:

Consider the following counter example.

interval_scheduling_3

The above mentioned algorithm selects 1 smaller request instead of 2 bigger ones. Hence, this algorithm is not optimal.