Activity Selection Problem Questions and Answers

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Activity Selection Problem”.

1. Which of the following approach should be used to find the solution of the activity selection problem?
a) Greedy approach
b) Divide and conquer
c) Brute-force approach
d) Dynamic programming
View Answer

Answer: a
Explanation: To find the solution of the activity selection problem, greedy approach should be used. Since we want to find the maximum number of activities that can be carried out in a particular time interval, this approach will greedily choose and give an optimal solution.

2. Suppose two activities A and B, having start and finish time as S_A, F_A and S_B, F_B respectively. Both the activities are said to be compatible, under which of the following condition?
a) S_A = F_B
b) S_A > F_B
c) S_A >= F_B or S_B >= F_A
d) S_A >= F_B and S_B = F_A
View Answer

Answer: c
Explanation: Two activities A and B are said to be compatible if the intervals [S_A, F_A) and [S_B, F_B) do not overlap, i.e., they are disjoint. The activity-selection problem optimizes to select a maximum size subset of mutually compatible activities. Hence, A and B are said to be compatible, if S_A >= F_B or S_B >= F_A.

3. Consider the following algorithm to find the solution of the activity selection problem. Which of the following option is best suited to fill the blank?

Sort the given activity List 
display the first activity 
set i = 1
for j = 1 to n-1 do
  if begin time of activity[j] >= completion of activity[i] then
      ___________
      i = j

a) display the ith activity
b) display the jth activity
c) discard the activity
d) increment j
View Answer

Answer: b
Explanation: To find the solution of the activity selection problem, firstly, sort the given activities in ascending order according to their finish time. Display the first activity. Select and display the new activity only if its starting time is greater than or equal to the previously selected activity’s finish time. Repeat till all the activities are checked.

Note: Join free Sanfoundry classes at Telegram or Youtube

4. Consider the following number of activities with their start and finish time given below. In which sequence will the activity be selected in order to maximize the number of activities, without any conflicts?

Activity	Starting time	Finish time
A1	1	2
A2	2	5
A3	1	5
A4	3	6
A5	6	8
A6	4	9

a) A1, A2, A5
b) A1, A2, A3, A4
c) A1, A3, A5
d) A1, A2, A5, A6
View Answer

Answer: a
Explanation: Following activities should be selected: A1 – activity started at 1 and ends at 2. A2 – activity started at 2 and ends at 5. A5 – activity started at 6 and ends at 8.

5. Time complexity to find the solution of activity selection problem takes O(n log n) time, when the list is not sorted.
a) True
b) False
View Answer

Answer: a
Explanation: The first step to find the solution of activity selection problem is to sort the activities according to the finish time, which takes O(log n) time. After sorting, we can find the solution using the greedy approach, by checking all the activities once. Hence, for n activities, it takes O(n log n) time if the list is not sorted.

6. The solution of the activity selection problem can have two overlapping activities in a particular time interval.
a) True
b) False
View Answer

Answer: b
Explanation: Given a set of activities, with start and finish time, each activity should use a common resource (for e.g. lecture hall). Its objective is to maximize the number of compatible activities that use the resource. Hence, it cannot have two overlapping activities in a particular time interval.

7. Consider the following number of activities with their start and finish time given below. Which of following activity will be left out?

Activity	Starting time	Finish time
A1	1	2
A2	3	5
A3	4	6
A4	5	8

a) A1
b) A2
c) A3
d) A4
View Answer

Answer: c
Explanation: The activities should be selected are: A1 – activity started at: 1 and ends at 2. A2 – activity started at: 3 and ends at 5. A4 – activity started at: 5 and ends at 8. Hence, activity A3 wouldn’t be selected because it starts at 4 but the previous activity ended at 5.

8. Which among the following represents best-case time complexity for activity selection problem?
a) O(n)
b) O(1)
c) O(n²)
d) O(n² * (log n)
View Answer

Answer: a
Explanation: Suppose, n activities with their start and finish time are given. We have to select the maximum number of activities, but at the same time only one activity can be carried out in a particular time interval. The best-case occurs when the given list is already sorted, which only requires checking all the activities once. Hence, the best-case time complexity for the activity selection problem will be O(n).

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

« Prev - Fractional Knapsack Problem Multiple Choice Questions and Answers (MCQs)

» Next - Huffman Code Multiple Choice Questions and Answers (MCQs)

Related Posts:

Recommended Articles: