Advanced Algorithms End Term: 3 September 2023, Set QPE1-S1 (May 2023 term)

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?

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 - 5
3 - 7
6 - 9
8 - 10

Instance 2:

The number of classes is N = 4
The timings of the classes are given by:
2 - 5
6 - 10
11 - 15
1 - 10

Instance 3:

The number of classes is N = 4
The timings of the classes are given by:
1 - 5
6 - 8
9 - 11
12 - 15

True or false?