Question 1: Recall the Dance Class problem: Problem Definition Dance …

Recall the Dance Class problem:

Problem Definition

Dance Classes

Input: A collection of $n$ intervals given by their left and right endpoints $(s_1, f_1), \ldots, (s_n, f_n)$, where $s_i < f_i$ for all $1 \leqslant i \leqslant n$.

Question: What is the size of the largest collection of mutually pairwise non-overlapping intervals?

Consider the greedy approach to the problem where we repeat the following until there are no intervals left:

select the shortest interval, eliminating ties arbitrarily, add it to our solution and eliminate all overlapping intervals.

On which of the following instances will this algorithm produce a suboptimal answer?

Instance 1:

The number of classes is N = 4
The timings of the classes are given by:
1 - 2
3 - 4
5 - 6
7 - 8

Instance 2:

The number of classes is N = 4
The timings of the classes are given by:
4 - 5
3 - 6
2 - 7
1 - 8

Instance 3:

The number of classes is N = 4
The timings of the classes are given by:
1 - 7
8 - 15
6 - 9
16 - 20