Activity Selection Problem in DSA C++ - Execution Trace

Concept Flow - Activity Selection Problem

Sort activities by finish time

↓

Select first activity

↓

For each next activity

↓

Check if start >= last selected finish?

↓

Select activity

↓

Repeat until all activities checked

↓

Done

Sort activities by finish time, then pick the earliest finishing activity that starts after the last selected one, repeat until all are checked.

Execution Sample

DSA C++

activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in range(1, len(activities)):
  if activities[i][0] >= selected[-1][1]:
    selected.append(activities[i])

Select maximum activities that don't overlap by sorting and greedy selection.

Execution Table

Step	Operation	Selected Activities	Current Activity	Check Condition	Action	Visual State
1	Sort activities by finish time	[]	N/A	N/A	Sorted list	[(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)] sorted to [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
2	Select first activity	[(1,4)]	(1,4)	N/A	Select	Selected: (1,4)
3	Check next activity	[(1,4)]	(3,5)	3 >= 4? False	Skip	Selected: (1,4)
4	Check next activity	[(1,4)]	(0,6)	0 >= 4? False	Skip	Selected: (1,4)
5	Check next activity	[(1,4)]	(5,7)	5 >= 4? True	Select	Selected: (1,4), (5,7)
6	Check next activity	[(1,4),(5,7)]	(3,9)	3 >= 7? False	Skip	Selected: (1,4), (5,7)
7	Check next activity	[(1,4),(5,7)]	(5,9)	5 >= 7? False	Skip	Selected: (1,4), (5,7)
8	Check next activity	[(1,4),(5,7)]	(6,10)	6 >= 7? False	Skip	Selected: (1,4), (5,7)
9	Check next activity	[(1,4),(5,7)]	(8,11)	8 >= 7? True	Select	Selected: (1,4), (5,7), (8,11)
10	Check next activity	[(1,4),(5,7),(8,11)]	(8,12)	8 >= 11? False	Skip	Selected: (1,4), (5,7), (8,11)
11	Check next activity	[(1,4),(5,7),(8,11)]	(2,14)	2 >= 11? False	Skip	Selected: (1,4), (5,7), (8,11)
12	Check next activity	[(1,4),(5,7),(8,11)]	(12,16)	12 >= 11? True	Select	Selected: (1,4), (5,7), (8,11), (12,16)
13	All activities checked	[(1,4),(5,7),(8,11),(12,16)]	N/A	N/A	Done	Final selection: (1,4), (5,7), (8,11), (12,16)

💡 All activities checked, selection complete.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 12	Final
Selected Activities	[]	[(1,4)]	[(1,4),(5,7)]	[(1,4),(5,7),(8,11)]	[(1,4),(5,7),(8,11),(12,16)]	[(1,4),(5,7),(8,11),(12,16)]
Current Activity	N/A	(1,4)	(5,7)	(8,11)	(12,16)	N/A
Last Selected Finish Time	N/A	4	7	11	16	16

Key Moments - 3 Insights

Why do we sort activities by finish time first?

Sorting by finish time ensures we always pick the activity that frees the schedule earliest, allowing more activities to fit later. See step 1 in execution_table.

Why do we compare the start time of the current activity with the finish time of the last selected activity?

To avoid overlapping activities, we only select the current activity if it starts after or exactly when the last selected activity finishes. See steps 3, 5, 9, and 12 in execution_table.

What happens if an activity starts before the last selected activity finishes?

We skip that activity because it overlaps and cannot be selected. This is shown in steps 3, 4, 6, 7, 8, 10, and 11 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the selected activities list after this step?

A [(5,7)]

B [(1,4)]

C [(1,4), (5,7)]

D []

💡 Hint

Check the 'Selected Activities' column at step 5 in execution_table.

At which step does the condition 'start >= last finish' become false for activity (3,5)?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Check Condition' column for activity (3,5) in execution_table.

If the activity (8,12) had a finish time of 10 instead of 12, how would the selection change?

A It would be selected after (8,11)

B It would be selected instead of (8,11)

C It would be skipped as before

D It would be selected before (5,7)

💡 Hint

Consider the sorting by finish time and the selection condition in execution_table.

Concept Snapshot

Activity Selection Problem:
- Sort activities by finish time
- Select first activity
- For each next activity, select if start >= last selected finish
- Skip otherwise
- Result: maximum non-overlapping activities

Full Transcript

The Activity Selection Problem finds the maximum number of activities that don't overlap. We first sort activities by their finish times. Then we pick the first activity. For each next activity, we check if its start time is at or after the finish time of the last selected activity. If yes, we select it; if no, we skip it. This greedy approach ensures the maximum number of activities are selected without overlap. The execution table shows each step, the current activity checked, the condition evaluated, and the selected activities list updated accordingly.

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