Activity Selection Problem in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Activity Selection

What is the output of the following C++ code that selects the maximum number of activities that don't overlap?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start, finish;
};

bool activityCompare(Activity s1, Activity s2) {
    return (s1.finish < s2.finish);
}

int main() {
    vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    sort(activities.begin(), activities.end(), activityCompare);
    
    int count = 1;
    int last_finish = activities[0].finish;
    cout << "Selected activities (start, finish): (" << activities[0].start << ", " << activities[0].finish << ")";
    
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= last_finish) {
            cout << " -> (" << activities[i].start << ", " << activities[i].finish << ")";
            last_finish = activities[i].finish;
            count++;
        }
    }
    cout << "\nTotal selected: " << count << endl;
    return 0;
}

A

Selected activities (start, finish): (0, 6) -> (6, 7) -> (8, 9)
Total selected: 3

B

Selected activities (start, finish): (1, 4) -> (5, 7) -> (8, 9)
Total selected: 3

C

Selected activities (start, finish): (1, 4) -> (3, 5) -> (5, 7) -> (8, 9)
Total selected: 4

D

Selected activities (start, finish): (1, 4) -> (5, 9)
Total selected: 2

💡 Hint

Sort activities by their finish time and pick the earliest finishing activity first.

The greedy approach sorts activities by finish time and selects the first activity. Then it selects the next activity whose start time is after or equal to the last selected activity's finish time. This ensures maximum number of non-overlapping activities.

🧠 Conceptual

intermediate

Key Idea Behind Activity Selection Problem

Which of the following best describes the key idea behind the greedy solution to the Activity Selection Problem?

A Always select the activity that finishes earliest among the remaining activities.

B Always select the activity with the shortest duration first.

C Always select the activity with the earliest start time first.

D Always select the activity that starts latest among the remaining activities.

💡 Hint

Think about which choice leaves the most room for other activities.

Selecting the activity that finishes earliest leaves the maximum remaining time for other activities, allowing the maximum number of activities to be selected.

🔧 Debug

advanced

Identify the Bug in Activity Selection Code

What error will the following code produce when run, and why?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start, finish;
};

bool activityCompare(Activity s1, Activity s2) {
    return (s1.start < s2.start);
}

int main() {
    vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    sort(activities.begin(), activities.end(), activityCompare);
    
    int count = 1;
    int last_finish = activities[0].finish;
    cout << "Selected activities (start, finish): (" << activities[0].start << ", " << activities[0].finish << ")";
    
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= last_finish) {
            cout << " -> (" << activities[i].start << ", " << activities[i].finish << ")";
            last_finish = activities[i].finish;
            count++;
        }
    }
    cout << "\nTotal selected: " << count << endl;
    return 0;
}

A The code causes a runtime error due to accessing out-of-bounds vector elements.

B The code runs correctly and outputs the maximum number of activities.

C The code outputs fewer activities than the optimal solution because it sorts by start time instead of finish time.

D The code causes a compilation error because the comparison function has wrong syntax.

💡 Hint

Check the sorting criteria and how it affects the greedy choice.

Sorting by start time does not guarantee the earliest finishing activity is chosen first, so the greedy approach fails to select the maximum number of activities.

🚀 Application

advanced

Maximum Number of Activities Selected

Given the activities with start and finish times: (2, 3), (1, 4), (3, 5), (0, 7), (5, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14), how many activities can be selected using the greedy activity selection algorithm?

A 4

B 6

C 7

D 5

💡 Hint

Sort activities by finish time and select greedily.

After sorting by finish time, the selected activities are (2,3), (3,5), (5,8), (8,11), (12,14), (8,12) is skipped because it overlaps with (8,11), so total 5 activities can be selected.

🧠 Conceptual

expert

Why Does Greedy Work for Activity Selection?

Why does the greedy algorithm that selects the earliest finishing activity at each step guarantee an optimal solution for the Activity Selection Problem?

A Because the problem has overlapping subproblems and optimal substructure, and earliest finishing activity leaves maximum room for others.

B Because selecting the earliest starting activity always leads to the maximum number of activities.

C Because the problem can be solved using dynamic programming only, and greedy is a heuristic.

D Because the activities are always sorted by duration, ensuring the shortest activities are selected first.

💡 Hint

Think about the properties that allow greedy algorithms to be optimal.

The problem exhibits optimal substructure and greedy choice property: choosing the earliest finishing activity leaves the largest possible remaining time for other activities, ensuring an optimal solution.

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