Activity Selection Problem in DSA C++ - Deep Dive

Overview - Activity Selection Problem

What is it?

The Activity Selection Problem is about choosing the maximum number of activities that don't overlap in time. Each activity has a start time and an end time. The goal is to select as many activities as possible so that no two chosen activities happen at the same time. This helps in scheduling tasks efficiently.

Why it matters

Without this problem's solution, we might waste time or resources by scheduling overlapping activities. For example, if you book two meetings at the same time, you can't attend both. Solving this problem helps in planning events, managing resources, and optimizing time in real life and computer systems.

Where it fits

Before learning this, you should understand arrays and sorting basics. After this, you can explore more complex scheduling problems like interval partitioning or dynamic programming approaches for weighted activities.

Mental Model

Core Idea

Pick activities that finish earliest to leave room for more activities later.

Think of it like...

Imagine you have a single meeting room and many people want to use it. To fit the most meetings, you always let the meeting that ends soonest happen first, then pick the next meeting that starts after it ends, and so on.

Activities sorted by finish time:

Start: 1  3  0  5  8  5
Finish:2  4  6  7  9  9

Selection process:
[1,2] -> [3,4] -> [5,7] -> [8,9]

Result: 4 activities selected without overlap.

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what activities are and how start and end times define them.

Activities are tasks with a start time and an end time. For example, Activity A starts at 1 and ends at 2. Two activities overlap if one starts before the other ends. The problem is to pick the largest set of activities that don't overlap.

Result

You understand that overlapping activities cannot be chosen together.

Knowing what counts as overlapping is key to solving scheduling problems.

2

Foundation

Sorting Activities by Finish Time

Concept: Sort activities by their finishing times to prepare for selection.

Given a list of activities, sort them so the one that finishes earliest comes first. For example, activities with finish times [4, 2, 3] become [2, 3, 4]. Sorting helps us pick activities that free up time quickly.

Result

Activities are ordered to consider earliest finishing ones first.

Sorting by finish time sets the stage for a greedy choice that leads to the best solution.

3

Intermediate

Greedy Selection Strategy

🤔Before reading on: Do you think picking the longest activity first or the earliest finishing activity first leads to more total activities? Commit to your answer.

Concept: Choose the next activity that starts after the last selected activity ends, always picking the earliest finishing one available.

Start with the first activity (earliest finish). Then, for each next activity, if its start time is after or equal to the last chosen activity's finish time, select it. Repeat until no more activities fit.

Result

You get the maximum number of non-overlapping activities.

Choosing the earliest finishing activity leaves the most room for future activities, maximizing total count.

4

Intermediate

Implementing the Algorithm in C++

🤔Before reading on: Do you think a simple loop with conditions can select activities after sorting, or do you need complex data structures? Commit to your answer.

Concept: Use a loop to iterate over sorted activities and pick compatible ones.

Code snippet: #include #include #include struct Activity { int start, finish; }; bool compare(Activity a, Activity b) { return a.finish < b.finish; } int selectActivities(std::vector &activities) { std::sort(activities.begin(), activities.end(), compare); int count = 1; // first activity always selected int last_finish = activities[0].finish; for (int i = 1; i < activities.size(); i++) { if (activities[i].start >= last_finish) { count++; last_finish = activities[i].finish; } } return count; } int main() { std::vector activities = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}}; std::cout << selectActivities(activities) << std::endl; return 0; }

Result

Output: 4

A simple loop after sorting is enough to solve the problem efficiently.

5

Intermediate

Dry Run with Example Activities

🤔Before reading on: How many activities do you think will be selected from the example list? Commit to your answer.

Concept: Walk through the algorithm step-by-step with a real example.

Activities: (start, finish) (1,2), (3,4), (0,6), (5,7), (8,9), (5,9) Sorted by finish time: (1,2), (3,4), (0,6), (5,7), (8,9), (5,9) Select (1,2) Next (3,4) starts at 3 >= 2, select Next (0,6) starts at 0 < 4, skip Next (5,7) starts at 5 >= 4, select Next (8,9) starts at 8 >= 7, select Next (5,9) starts at 5 < 9, skip Total selected: 4

Result

Selected activities count: 4

Step-by-step tracing confirms the greedy choice leads to maximum selection.

6

Advanced

Time Complexity and Optimization

🤔Before reading on: Do you think sorting or selection dominates the time cost? Commit to your answer.

Concept: Analyze the algorithm's efficiency and understand its limits.

Sorting takes O(n log n) time, where n is the number of activities. The selection loop runs in O(n). Overall complexity is O(n log n). This is efficient for large inputs. No extra data structures are needed, keeping memory use low.

Result

Algorithm runs efficiently even for large activity lists.

Understanding complexity helps predict performance and scalability.

7

Expert

Extensions: Weighted Activity Selection

🤔Before reading on: Do you think the greedy approach works if activities have different values or weights? Commit to your answer.

Concept: When activities have weights (importance), greedy fails; dynamic programming is needed.

If each activity has a weight, picking earliest finishing may not maximize total weight. Instead, use dynamic programming to find the set with maximum total weight without overlap. This involves sorting, binary searching for compatible activities, and building a DP table.

Result

Weighted activity selection requires more complex algorithms than greedy.

Knowing greedy limits prevents wrong assumptions and guides toward correct advanced solutions.

Under the Hood

The algorithm sorts activities by their finish times, then iterates through them, always picking the next activity that starts after the last selected one ends. This greedy choice works because selecting the earliest finishing activity leaves the maximum remaining time for others. Internally, sorting arranges data for linear scanning, and the selection loop checks compatibility by comparing start and finish times.

Why designed this way?

This approach was designed to solve scheduling efficiently without checking all subsets, which would be slow. The greedy method exploits the problem's optimal substructure: locally optimal choices lead to a globally optimal solution. Alternatives like brute force were rejected due to exponential time.

Activities sorted by finish time:

┌───────────────┐
│ Activity List │
└──────┬────────┘
       │ Sort by finish time
       ▼
┌─────────────────────────────┐
│ (1,2) (3,4) (0,6) (5,7) ... │
└──────┬──────────────────────┘
       │ Iterate and select if start >= last finish
       ▼
┌─────────────────────────────┐
│ Selected activities sequence │
│ (1,2) -> (3,4) -> (5,7) ... │
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does picking the longest activity first always maximize the number of activities? Commit yes or no.

Common Belief: Choosing the longest activity first will maximize total usage and number of activities.

Reality: Picking the longest activity first can block many shorter activities, reducing total count.

Why it matters: This misconception leads to fewer scheduled activities and inefficient use of time or resources.

Quick: Can the greedy approach solve weighted activity selection optimally? Commit yes or no.

Common Belief: The greedy method works for all activity selection problems, including weighted ones.

Reality: Greedy fails for weighted activities; dynamic programming is required.

Why it matters: Using greedy for weighted problems causes suboptimal schedules and lost value.

Quick: Does sorting by start time instead of finish time yield the best solution? Commit yes or no.

Common Belief: Sorting activities by start time is enough to select the maximum number of activities.

Reality: Sorting by finish time is necessary; sorting by start time can miss optimal selections.

Why it matters: Wrong sorting leads to incorrect schedules and fewer activities selected.

Expert Zone

1

The greedy choice property depends on activities being non-weighted and intervals being closed-open or closed; subtle differences in interval definitions can affect correctness.

2

In practice, stable sorting by finish time preserves original order, which can be important when activities have equal finish times.

3

Binary search can optimize finding the next compatible activity in weighted versions, reducing complexity from O(n^2) to O(n log n).

When NOT to use

Do not use the greedy approach when activities have weights or values; instead, use dynamic programming. Also avoid greedy if activities can partially overlap or have complex constraints like resource limits.

Production Patterns

Used in CPU job scheduling, booking systems, and event planning software. Often combined with priority queues or interval trees for dynamic activity insertion and removal.

Connections

Interval Scheduling

Activity Selection is a classic example of interval scheduling problems.

Understanding activity selection helps grasp broader interval scheduling challenges in operating systems and networking.

Dynamic Programming

Weighted activity selection builds on the greedy approach but requires dynamic programming.

Knowing greedy limits guides learners to dynamic programming for more complex optimization.

Project Management

Activity selection principles apply to scheduling tasks and resources in project timelines.

Learning this problem aids in real-world project planning and resource allocation.

Common Pitfalls

#1 Selecting activities based on earliest start time instead of earliest finish time.

Wrong approach:

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

Correct approach:

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

Root cause:

Misunderstanding that earliest finish time is the key to maximizing activity count.

#2 Trying to select overlapping activities by ignoring start and finish comparisons.

Wrong approach:

for (auto &act : activities) { selected.push_back(act); } // no checks

Correct approach:

for (auto &act : activities) { if (act.start >= last_finish) { selected.push_back(act); last_finish = act.finish; } }

Root cause:

Not checking compatibility leads to invalid schedules with overlaps.

#3 Using greedy approach for weighted activities expecting optimal total weight.

Wrong approach:

Select activities greedily by earliest finish time ignoring weights.

Correct approach:

Use dynamic programming with binary search to find maximum weighted set.

Root cause:

Assuming greedy works for all variants without considering weights.

Key Takeaways

The Activity Selection Problem finds the largest set of non-overlapping activities by always picking the earliest finishing activity next.

Sorting activities by their finish times is essential to enable the greedy selection strategy.

Greedy selection works because choosing the earliest finishing activity leaves maximum room for others, ensuring optimality.

This problem teaches a fundamental greedy algorithm pattern used in scheduling and resource allocation.

For weighted activities, greedy fails and dynamic programming is required, highlighting the importance of understanding problem constraints.

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