Consider the following minimize gaps interval scheduling problem: Given is a global start time S and finish time F. Given also is a set of n intervals where the i-th interval starts at time s_i and ends at time fi , S s_i f_i F, for i {0, . . . , n 1}. Find a set of non-overlapping intervals so that the overall time from S to F not covered by the selected intervals is as small as possible (we refer to this time as gap time).

Example: S = 0, F = 10, and the intervals are (1, 4),(2, 7),(4, 5),(6, 10),(8, 9). If we select intervals (1, 4),(4, 5),(6, 10), then the time between 0 and 10 that is not covered by the intervals is (0, 1) and (5, 6) total time 2. This is the smallest possible overall gap time. Note that in the case when the end time of one interval equals the start time of a second interval, those two intervals are considered to be compatible (e.g. (1, 4) and (4, 5)).

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 6= j such that s_j f_i 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 s_i : the recursive call will have S_new = S and F_new = s_i . Similarly, recursively do the same selection process with intervals that start at or after f_j : now S_new = f_j and F_new = F. If there is no such pair of 1 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.