Question

Consider the following greedy strategies for this problem: 1. Select the earliest finishing interval and discard overlapping intervals. Keep doing this until all intervals have been eliminated (either selected or discarded). 2. Select the earliest starting interval and discard overlapping intervals. Keep doing this until all intervals have been eliminated (either selected or discarded). 3. Select the pair of non-overlapping intervals that have the smallest gap between them: find a pair of intervals i # j such that s; - fi > 0 is the smallest possible. Select both intervals and discard overlapping intervals. Recursively do the same selection process with intervals that finish at or before si: the recursive call will have Snew = S and Fnew = si. Similarly, recursively do the same selection process with intervals that start at or after fi: now Snew = f; and Fnew = F. If there is no such pair of intervals, select a single interval that minimizes the gap between S and F (do not make any further recursive calls). None of these strategies works all the time. Find a counterexample for each strategy. In other words, for each strategy, • find a set of intervals and S and F so that the strategy does not produce an optimal solution, • highlight intervals selected by the strategy and state the corresponding gap time, and • highlight intervals in an optimal solution (one that minimizes the overall gap time) and state the corresponding gap time.

Answer 1

Solution :-

1.)  Earliest finishing interval is the optimal greedy solution so there is no counter case.

2.)  Take the example of 3 intervals (2,12), (3,5) and (6,9) then using earliest start time algo we can only choose (2,12) but optimal solution will be 2 (choosing (3,5) and (6,9) ).

3.) Take the example of following intervals :- (2,9), (3,6), (8,12), (10,17), (15,19)

using given algorithm we will choose pairs (2,9) and (10,17) because of having minimum gap interval and then discard the others because they are not compatible with these.

But optimal answer is 3. we can choose the intervals (3,6), (8,12) and (15,19).

If you like the solution please give it a thumbs up!! and if have further queries please write in the comment section.