Activity Selection Problem in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Activity Selection Problem?

To select the maximum number of activities that don't overlap in time from a given set of activities, each with a start and finish time.

beginner

Which algorithmic approach is commonly used to solve the Activity Selection Problem efficiently?

The greedy algorithm approach, which selects activities based on earliest finish time to maximize the number of non-overlapping activities.

intermediate

In the Activity Selection Problem, why do we sort activities by their finish times before selecting them?

Sorting by finish times ensures that when we pick an activity, it leaves the maximum remaining time for other activities, helping to maximize the total count.

intermediate

What is the time complexity of the greedy solution to the Activity Selection Problem after sorting?

O(n log n) due to sorting the activities by finish time, where n is the number of activities. The selection process itself is O(n).

advanced

Explain the greedy choice property in the context of the Activity Selection Problem.

The greedy choice property means that choosing the activity that finishes earliest is always part of an optimal solution, allowing us to build the solution step-by-step.

What is the first step in the greedy solution to the Activity Selection Problem?

A Sort activities by their finish times

B Sort activities by their start times

C Select the longest activity first

D Select activities randomly

Sorting activities by their finish times helps to pick the earliest finishing activity first, which is key to the greedy approach.

After selecting an activity, what is the next criterion to select the next activity?

A The activity with the earliest start time

B The activity with the earliest finish time that starts after the last selected activity finishes

C The activity with the longest duration

D The activity with the latest finish time

We pick the next activity that starts after the last selected activity finishes and has the earliest finish time.

What does the Activity Selection Problem demonstrate about greedy algorithms?

A Greedy algorithms require backtracking

B Greedy algorithms always fail

C Greedy algorithms are slower than dynamic programming

D Greedy algorithms can find an optimal solution for some problems

The problem shows that greedy algorithms can find optimal solutions when the problem has the greedy choice property.

If two activities overlap, what does the greedy algorithm do?

A Select both activities

B Select the one with the later start time

C Select the one with the earlier finish time

D Skip both activities

The algorithm selects the activity that finishes earlier to maximize the chance of selecting more activities.

What is the output of the Activity Selection Problem?

A The maximum number of non-overlapping activities selected

B The minimum number of activities to cover all time

C The total duration of all activities

D The list of overlapping activities

The problem outputs the maximum number of activities that can be scheduled without overlapping.

Describe the steps to solve the Activity Selection Problem using a greedy algorithm.

Think about how sorting helps and how you pick activities one by one.

Explain why the greedy choice of selecting the earliest finishing activity leads to an optimal solution in the Activity Selection Problem.

Consider how choosing the earliest finishing activity affects the rest of the schedule.

Practice

1. What is the main goal of the Activity Selection Problem?

easy

A. Calculate the total time of all activities

B. Find the activity with the longest duration

C. Sort activities by their start time

D. Select the maximum number of activities that don't overlap in time

Solution

1. Step 1: Understand the problem goal

   The Activity Selection Problem aims to choose the largest set of activities that do not overlap in their time intervals.

2. Step 2: Identify the correct goal

   Among the options, only selecting the maximum number of non-overlapping activities matches the problem's goal.

3. Final Answer:

   Select the maximum number of activities that don't overlap in time -> Option D

4. Quick Check:

   Goal = Max non-overlapping activities [OK]

Hint: Focus on maximizing non-overlapping activities [OK]

Common Mistakes:

• Confusing longest duration with maximum count
• Sorting by start time only
• Summing all activity durations

2. Which of the following is the correct way to sort activities by their finish time in C++ using std::sort?

easy

A. std::sort(activities.begin(), activities.end(), [](auto &a, auto &b){ return a.start < b.start; });

B. std::sort(activities.begin(), activities.end(), [](auto &a, auto &b){ return a.finish < b.finish; });

C. std::sort(activities.begin(), activities.end());

D. std::sort(activities.begin(), activities.end(), [](auto &a, auto &b){ return a.duration > b.duration; });

Solution

1. Step 1: Identify sorting criteria for Activity Selection

   Activities must be sorted by their finish time to apply the greedy approach correctly.

2. Step 2: Match sorting code to finish time

   std::sort(activities.begin(), activities.end(), [](auto &a, auto &b){ return a.finish < b.finish; }); sorts activities by their finish time using a lambda comparator, which is the correct syntax.

3. Final Answer:

   std::sort(activities.begin(), activities.end(), [](auto &a, auto &b){ return a.finish < b.finish; }); -> Option B

4. Quick Check:

   Sort by finish time = std::sort(activities.begin(), activities.end(), [](auto &a, auto &b){ return a.finish < b.finish; }); [OK]

Hint: Sort activities by finish time using a lambda [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Using default sort without comparator on custom structs
• Sorting by duration which is not needed

3. What will be the output of the following C++ code snippet for the Activity Selection Problem?

struct Activity {
  int start, finish;
};

Activity activities[] = {{1, 3}, {2, 5}, {4, 7}, {6, 9}};
int n = 4;

std::sort(activities, activities + n, [](Activity a, Activity b) { return a.finish < b.finish; });

int count = 1, last_finish = activities[0].finish;
for (int i = 1; i < n; i++) {
  if (activities[i].start >= last_finish) {
    count++;
    last_finish = activities[i].finish;
  }
}
std::cout << count;

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Sort activities by finish time

   Sorted activities by finish time: (1,3), (2,5), (4,7), (6,9)

2. Step 2: Select activities greedily

   Start with first activity (1,3). Next, (2,5) starts at 2 < 3, skip. (4,7) starts at 4 >= 3, select, last_finish=7. (6,9) starts at 6 < 7, skip. Total selected = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Max non-overlapping activities = 3 [OK]

Hint: Sort by finish time, pick next starting after last finish [OK]

Common Mistakes:

• Counting overlapping activities
• Not updating last_finish correctly
• Assuming all activities can be selected

4. Identify the error in the following C++ code snippet for the Activity Selection Problem:

struct Activity {
  int start, finish;
};

Activity activities[] = {{1, 2}, {3, 4}, {0, 6}, {5, 7}};
int n = 4;

std::sort(activities, activities + n, [](Activity a, Activity b) { return a.start < b.start; });

int count = 1, last_finish = activities[0].finish;
for (int i = 1; i < n; i++) {
  if (activities[i].start >= last_finish) {
    count++;
    last_finish = activities[i].finish;
  }
}
std::cout << count;

medium

A. Not initializing count to zero

B. Using wrong loop range in for loop

C. Sorting by start time instead of finish time

D. Comparing start time with finish time incorrectly

Solution

1. Step 1: Check sorting criteria

   The code sorts activities by start time, but the greedy approach requires sorting by finish time.

2. Step 2: Understand impact of wrong sorting

   Sorting by start time can cause incorrect selection of activities, leading to wrong count.

3. Final Answer:

   Sorting by start time instead of finish time -> Option C

4. Quick Check:

   Sort by finish time needed, not start time [OK]

Hint: Always sort by finish time for activity selection [OK]

Common Mistakes:

• Sorting by start time
• Incorrect initialization of count
• Wrong loop boundaries

5. Given the following activities with start and finish times:

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]

Using the Activity Selection Problem approach, which set of activities represents the maximum number of non-overlapping activities?

hard

A. [(1, 4), (5, 7), (8, 9)]

B. [(0, 6), (5, 9)]

C. [(3, 5), (5, 7), (8, 9)]

D. [(1, 4), (3, 5), (5, 9)]

Solution

1. Step 1: Sort activities by finish time

   Sorted by finish time: (1,4), (3,5), (0,6), (5,7), (8,9), (5,9)

2. Step 2: Select activities greedily

   Select (1,4). Next, (3,5) overlaps with (1,4), skip. (0,6) overlaps, skip. (5,7) starts after 4, select. (8,9) starts after 7, select. (5,9) overlaps with (5,7), skip.

3. Final Answer:

   [(1, 4), (5, 7), (8, 9)] -> Option A

4. Quick Check:

   Max non-overlapping set = [(1, 4), (5, 7), (8, 9)] [OK]

Hint: Sort by finish time, pick next starting after last finish [OK]

Common Mistakes:

• Choosing overlapping activities
• Not sorting before selection
• Selecting activities with later finish times first