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?

No→Skip activity

Yes↓

Select activity

↓

Repeat until all activities checked

↓

Return selected activities

Sort activities by finish time, then pick the earliest finishing compatible activities one by one.

Execution Sample

DSA C

activities = [(1,4),(3,5),(0,6),(5,7),(8,9),(5,9)];
// Sort by finish time
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
last_finish = activities[0][1]
for i in range(1, len(activities)):
    if activities[i][0] >= last_finish:
        selected.append(activities[i])
        last_finish = activities[i][1]

Select maximum number of non-overlapping activities by sorting and greedy selection.

Execution Table

Step	Operation	Current Activity (start, finish)	Last Selected Finish	Selected Activities	Action
1	Sort activities by finish time	-	-	[]	Original: [(1,4),(3,5),(0,6),(5,7),(8,9),(5,9)] sorted by finish time: [(1,4),(3,5),(0,6),(5,7),(8,9),(5,9)]
2	Select first activity	(1,4)	-	[(1,4)]	Select first activity (1,4)
3	Check next activity	(3,5)	4	[(1,4)]	3 < 4? No, skip (3,5)
4	Check next activity	(0,6)	4	[(1,4)]	0 < 4? No, skip (0,6)
5	Check next activity	(5,7)	4	[(1,4)]	5 >= 4? Yes, select (5,7)
6	Check next activity	(8,9)	7	[(1,4),(5,7)]	8 >= 7? Yes, select (8,9)
7	Check next activity	(5,9)	9	[(1,4),(5,7),(8,9)]	5 >= 9? No, skip (5,9)
8	End	-	9	[(1,4),(5,7),(8,9)]	All activities checked

💡 All activities checked, selection complete.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	Final
Selected Activities	[]	[(1,4)]	[(1,4),(5,7)]	[(1,4),(5,7),(8,9)]	[(1,4),(5,7),(8,9)]
Last Selected Finish	-	4	7	9	9
Current Activity	-	(1,4)	(5,7)	(5,9)	-

Key Moments - 3 Insights

Why do we sort activities by their 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 one finishes. See Steps 3, 5, 6, and 7.

Why do we always select the first activity after sorting?

Because the first activity finishes earliest, selecting it maximizes room for others. This is shown in Step 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the selected activities list after Step 5?

A [(1,4),(3,5)]

B [(1,4)]

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

D [(5,7)]

💡 Hint

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

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

A Step 4

B Step 7

C Step 6

D Step 3

💡 Hint

Look at Step 7 in execution_table under 'Action' and 'Current Activity'.

If the activity (5,7) was removed, what would be the selected activities after Step 7?

A [(1,4),(8,9)]

B [(1,4),(5,9),(8,9)]

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

D [(3,5),(8,9)]

💡 Hint

Without (5,7), the next compatible activity after (1,4) is (8,9). Check variable_tracker for selected activities.

Concept Snapshot

Activity Selection Problem:
- Sort activities by finish time
- Select first activity
- For each next activity, select if start >= last selected finish
- Repeat until all checked
- Result: max non-overlapping activities

Full Transcript

The Activity Selection Problem finds the maximum number of activities that don't overlap. First, we sort activities by their finish times. Then, we pick the first activity because it finishes earliest. Next, for each 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. We repeat this until all activities are checked. The selected activities form the largest set of non-overlapping activities.

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. Select the maximum number of activities that don't overlap in time

D. Sort activities by their start 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 C

4. Quick Check:

   Goal = Max non-overlapping activities [OK]

Hint: Choose activities that finish earliest to fit more [OK]

Common Mistakes:

• Confusing longest duration with maximum count
• Sorting by start time only
• Trying to sum all activity times

2. Which of the following C code snippets correctly sorts activities by their finish time for the Activity Selection Problem?

easy

A. qsort(activities, n, sizeof(Activity), compareStart);

B. qsort(activities, n, sizeof(Activity), compareFinish);

C. sort(activities, n, sizeof(Activity), compareDuration);

D. qsort(activities, n, sizeof(Activity), compareName);

Solution

1. Step 1: Identify sorting criteria

   For the Activity Selection Problem, activities must be sorted by their finish time to select the maximum number of non-overlapping activities.

2. Step 2: Match sorting function

   Only qsort with compareFinish sorts by finish time correctly.

3. Final Answer:

   qsort(activities, n, sizeof(Activity), compareFinish); -> Option B

4. Quick Check:

   Sort by finish time = qsort + compareFinish [OK]

Hint: Sort activities by finish time using qsort and compareFinish [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Using undefined compare functions
• Using wrong sorting function name

3. What is the output of the following C code snippet for the Activity Selection Problem?

typedef struct {
  int start;
  int finish;
} Activity;

Activity activities[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
int n = 6;

// Assume activities are sorted by finish time
int count = 1;
int last_finish = activities[0].finish;
for (int i = 1; i < n; i++) {
  if (activities[i].start >= last_finish) {
    count++;
    last_finish = activities[i].finish;
  }
}
printf("%d\n", count);

medium

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Trace the selection process

   Activities sorted by finish time: (1,4), (3,5), (0,6), (5,7), (8,9), (5,9). Start with count=1, last_finish=4.
   Check each activity:
   - (3,5): start 3 < 4, skip
   - (0,6): start 0 < 4, skip
   - (5,7): start 5 >= 4, select, count=2, last_finish=7
   - (8,9): start 8 >= 7, select, count=3, last_finish=9
   - (5,9): start 5 < 9, skip

2. Step 2: Final count of selected activities

   Total selected activities = 4

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Selected count = 4 [OK]

Hint: Count activities starting after last selected finish time [OK]

Common Mistakes:

• Not sorting activities by finish time
• Selecting overlapping activities
• Incorrectly updating last_finish

4. Identify the error in the following C code snippet for the Activity Selection Problem:

typedef struct {
  int start;
  int finish;
} Activity;

Activity activities[] = {{1, 3}, {2, 5}, {4, 7}};
int n = 3;

// Activities are sorted by finish time
int count = 0;
int last_finish = 0;
for (int i = 0; i < n; i++) {
  if (activities[i].start > last_finish) {
    count++;
    last_finish = activities[i].finish;
  }
}
printf("%d\n", count);

medium

A. The condition should be activities[i].start >= last_finish

B. The loop should start from i = 1, not 0

C. last_finish should be initialized to activities[0].finish

D. The activities array is not sorted

Solution

1. Step 1: Analyze the selection condition

   The condition uses '>' which excludes activities starting exactly at last_finish time. It should allow activities starting at or after last_finish, so '>=' is correct.

2. Step 2: Check other parts

   Starting loop at 0 and initializing last_finish to 0 is fine if condition is corrected. The activities are sorted as stated.

3. Final Answer:

   The condition should be activities[i].start >= last_finish -> Option A

4. Quick Check:

   Use >= to include activities starting at last finish [OK]

Hint: Use >= to allow activities starting exactly at last finish [OK]

Common Mistakes:

• Using > excludes valid activities
• Starting loop from 1 unnecessarily
• Wrong initialization of last_finish

5. Given the following activities with start and finish times:

Activities = [(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]

Which set of activities represents the maximum number of non-overlapping activities selected by the greedy algorithm?

hard

A. [(1, 2), (3, 4), (5, 7), (8, 9)]

B. [(0, 6), (5, 7), (8, 9)]

C. [(1, 2), (5, 9)]

D. [(3, 4), (5, 7), (8, 9)]

Solution

1. Step 1: Sort activities by finish time

   Sorted activities: (1,2), (3,4), (0,6), (5,7), (8,9), (5,9)

2. Step 2: Select activities greedily

   Select (1,2) first.
   Next, (3,4) starts after 2, select.
   (0,6) overlaps, skip.
   (5,7) starts after 4, select.
   (8,9) starts after 7, select.
   (5,9) overlaps, skip.
   Selected set: [(1,2), (3,4), (5,7), (8,9)]

3. Final Answer:

   [(1, 2), (3, 4), (5, 7), (8, 9)] -> Option A

4. Quick Check:

   Greedy selects max non-overlapping activities [OK]

Hint: Pick earliest finishing activities to maximize count [OK]

Common Mistakes:

• Choosing overlapping activities
• Not sorting by finish time
• Selecting longer activities first