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
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 SA, FA and SB, FB respectively. Both the activities are said to be compatible, under which of the following condition?
a) SA = FB
b) SA > FB
c) SA >= FB or SB >= FA
d) SA >= FB and SB = FA
View Answer
Explanation: Two activities A and B are said to be compatible if the intervals [SA, FA) and [SB, FB) 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 SA >= FB or SB >= FA.
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 = ja) display the ith activity
b) display the jth activity
c) discard the activity
d) increment j
View Answer
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.
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
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
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
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
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(n2)
d) O(n2 * (log n)
View Answer
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.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Apply for Computer Science Internship
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
- Check Programming Books
- Practice Programming MCQs
