Activity Selection Problem in DSA C++

Mental Model

Choose the maximum number of activities that don't overlap by always picking the earliest finishing activity first.

Analogy: Imagine scheduling meetings in one room. To fit the most meetings, always pick the meeting that ends soonest so the room becomes free earlier for the next meeting.

Activities: [start, end]
[1, 4] -> [3, 5] -> [0, 6] -> [5, 7] -> [8, 9] -> [5, 9]
↑start times sorted
We pick activities so none overlap.

Dry Run Walkthrough

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

Goal: Select the maximum number of non-overlapping activities.

Step 1: Sort activities by finish time

[1,4] -> [3,5] -> [0,6] -> [5,7] -> [5,9] -> [8,9]

Why: Sorting by finish time helps pick the earliest finishing activity first.

Step 2: Select first activity [1,4]

[1,4] (selected) -> [3,5] -> [0,6] -> [5,7] -> [5,9] -> [8,9]

Why: First activity always selected as it finishes earliest.

Step 3: Skip [3,5] because it starts before [1,4] ends

[1,4] (selected) -> [3,5] (skipped) -> [0,6] -> [5,7] -> [5,9] -> [8,9]

Why: Overlap with previously selected activity.

Step 4: Skip [0,6] because it starts before [1,4] ends

[1,4] (selected) -> [3,5] (skipped) -> [0,6] (skipped) -> [5,7] -> [5,9] -> [8,9]

Why: Overlap with previously selected activity.

Step 5: Select [5,7] because it starts after [1,4] ends

[1,4] (selected) -> [3,5] (skipped) -> [0,6] (skipped) -> [5,7] (selected) -> [5,9] -> [8,9]

Why: No overlap, can select.

Step 6: Skip [5,9] because it overlaps with [5,7]

[1,4] (selected) -> [3,5] (skipped) -> [0,6] (skipped) -> [5,7] (selected) -> [5,9] (skipped) -> [8,9]

Why: Overlap with previously selected activity.

Step 7: Select [8,9] because it starts after [5,7] ends

[1,4] (selected) -> [3,5] (skipped) -> [0,6] (skipped) -> [5,7] (selected) -> [5,9] (skipped) -> [8,9] (selected)

Why: No overlap, can select.

Result:

Selected activities: [1,4] -> [5,7] -> [8,9]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

struct Activity {
    int start, end;
};

// Comparator to sort activities by their finish time
bool compare(Activity a1, Activity a2) {
    return a1.end < a2.end;
}

std::vector<Activity> selectActivities(std::vector<Activity>& activities) {
    std::vector<Activity> selected;
    if (activities.empty()) return selected;

    // Sort activities by finish time
    std::sort(activities.begin(), activities.end(), compare);

    // Select the first activity
    selected.push_back(activities[0]);
    int last_end = activities[0].end;

    // Iterate over remaining activities
    for (size_t i = 1; i < activities.size(); ++i) {
        // If activity starts after or when last selected activity ends
        if (activities[i].start >= last_end) {
            selected.push_back(activities[i]);
            last_end = activities[i].end;
        }
    }
    return selected;
}

int main() {
    std::vector<Activity> activities = {{1,4}, {3,5}, {0,6}, {5,7}, {8,9}, {5,9}};
    std::vector<Activity> result = selectActivities(activities);

    for (const auto& act : result) {
        std::cout << "[" << act.start << "," << act.end << "] ";
    }
    std::cout << std::endl;
    return 0;
}

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

Sort activities by their finish time to pick earliest finishing first

selected.push_back(activities[0]);

Select the first activity as it finishes earliest

if (activities[i].start >= last_end) {

Check if current activity starts after last selected activity ends

selected.push_back(activities[i]);

Select current activity as it does not overlap

last_end = activities[i].end;

Update last_end to current activity's finish time

Output

[1,4] [5,7] [8,9] 

Complexity Analysis

Time: O(n log n) because we sort the activities by finish time and then iterate once through them

Space: O(n) because in worst case all activities can be selected and stored

vs Alternative: Naive approach tries all subsets with exponential time; greedy sorting approach is efficient and optimal

Edge Cases

empty list of activities

returns empty selection without error

DSA C++

if (activities.empty()) return selected;

all activities overlap

only the earliest finishing activity is selected

DSA C++

if (activities[i].start >= last_end) {

activities with same finish time

selects the first one encountered, others skipped if overlapping

DSA C++

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

When to Use This Pattern

When asked to schedule maximum non-overlapping intervals or tasks, reach for the Activity Selection greedy pattern because sorting by finish time leads to an optimal solution.

Common Mistakes

Mistake: Sorting activities by start time instead of finish time
Fix: Sort activities by their finish time to ensure earliest finishing activities are chosen first

Mistake: Selecting overlapping activities by not checking start time against last selected end time
Fix: Always check if current activity starts after or at the end time of last selected activity before selecting

Summary

Selects the maximum number of non-overlapping activities by always choosing the earliest finishing one next.

Use when you need to schedule tasks or events without overlap to maximize the count.

The key insight is sorting by finish time lets you greedily pick activities that leave room for more later.

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