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 select the interval with ---------, eliminating ties arbitrarily; add it to our solution and eliminate all overlapping intervals. Which of the following strategies guarantees an optimal result?

(D) the smallest right endpoint (i.e, a class that finishes earliest)

(B) the fewest overlaps with other intervals

(C) the smallest left endpoint (i.e, a class that starts earliest)

Advanced Algorithms · End Term · 3 Sept 2023 · May 2023 term · Set QPE1-S2

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

Question 8

+2 marksOne correct option

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 interval with ---------, eliminating ties arbitrarily; add it to our solution and eliminate all overlapping intervals.

Which of the following strategies guarantees an optimal result?

A
the shortest duration
B
the fewest overlaps with other intervals
C
the smallest left endpoint (i.e, a class that starts earliest)
D
the smallest right endpoint (i.e, a class that finishes earliest)

Show answer

Correct answer

D
the smallest right endpoint (i.e, a class that finishes earliest)

See the whole paper Take it as a mock test

Question 8 of 34 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 3 Sept 2023, in the May 2023 term (IIT M DEGREE ET1 EXAM QPE1 S2 03 Sep). It carries 2 marks.

This question was also asked in

Advanced Algorithms End Term — 3 Sept 2023, Set QPE1-S1 · question 8

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

Question 8

This question was also asked in

More questions from this paper