Activity Selection Problem in DSA C++ - Build from Scratch

Activity Selection Problem

📖 Scenario: You are organizing a conference and have a list of activities with their start and finish times. You want to select the maximum number of activities that don't overlap so attendees can participate in as many as possible.

🎯 Goal: Build a program that selects the maximum number of non-overlapping activities from a given list using the Activity Selection Problem approach.

📋 What You'll Learn

Create a vector of pairs called activities with given start and finish times

Create an integer variable n to store the number of activities

Sort the activities vector based on finish times

Implement the activity selection logic to choose maximum non-overlapping activities

Print the selected activities' start and finish times in order

💡 Why This Matters

🌍 Real World

Scheduling meetings, classes, or events to maximize usage of a shared resource without conflicts.

💼 Career

Useful for software engineers working on calendar apps, event planners, and operations managers optimizing resource allocation.

1

Create the list of activities

Create a vector of pairs called activities with these exact entries: {1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}.

DSA C++

#include 
#include 
#include 

int main() {
    // Create vector of pairs called activities with given start and finish times
    // Your code here
}

Hint

Use std::vector> to store start and finish times as pairs.

2

Set the number of activities

Create an integer variable called n and set it to the size of the activities vector.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    // Create integer n and set it to activities.size()
    // Your code here
}

Hint

Use int n = activities.size(); to get the number of activities.

3

Sort activities and select maximum non-overlapping

Sort the activities vector by their finish times using std::sort with a lambda. Then create a vector of pairs called selected to store chosen activities. Add the first activity to selected. Use a for loop with variable i from 1 to n-1 to check if the start time of activities[i] is greater or equal to the finish time of the last selected activity. If yes, add activities[i] to selected.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    int n = activities.size();
    // Sort activities by finish time
    // Create vector selected and add first activity
    // Use for loop from i = 1 to n-1 to select non-overlapping activities
    // Your code here
}

Hint

Sort by finish time using a lambda. Then pick the first activity. Loop through remaining activities and pick those starting after or at the finish time of last selected.

4

Print the selected activities

Use a for loop with variable activity to iterate over selected and print each activity's start and finish times separated by a space, each on a new line.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    int n = activities.size();

    std::sort(activities.begin(), activities.end(), [](const std::pair& a, const std::pair& b) {
        return a.second > selected;
    selected.push_back(activities[0]);

    for (int i = 1; i = selected.back().second) {
            selected.push_back(activities[i]);
        }
    }

    // Print each selected activity's start and finish times
    // Your code here
}

Hint

Use a range-based for loop to print each selected activity's start and finish times separated by a space.

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