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 you have a single meeting room and many meetings to schedule. To fit the most meetings, always pick the one that ends earliest so the room becomes free sooner for the next meeting.

Activities sorted by finish time:
[Activity1]---
       [Activity2]---
           [Activity3]---
                [Activity4]---

Dry Run Walkthrough

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

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

Step 1: Sort activities by finish time

[(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)] sorted to [(1,4), (3,5), (0,6), (5,7), (5,9), (8,9)]

Why: Sorting by finish time helps pick activities that free the room earliest.

Step 2: Select first activity (1,4)

Selected: (1,4)

Why: First activity always selected after sorting.

Step 3: Check next activity (3,5), start 3 < last finish 4, skip

Selected: (1,4)

Why: Activity overlaps with last selected, so skip.

Step 4: Check next activity (0,6), start 0 < 4, skip

Selected: (1,4)

Why: Overlaps with last selected, skip.

Step 5: Check next activity (5,7), start 5 >= 4, select

Selected: (1,4), (5,7)

Why: No overlap, select this activity.

Step 6: Check next activity (5,9), start 5 < 7, skip

Selected: (1,4), (5,7)

Why: Overlaps with last selected, skip.

Step 7: Check next activity (8,9), start 8 >= 7, select

Selected: (1,4), (5,7), (8,9)

Why: No overlap, select this activity.

Result:

Selected activities: (1,4) -> (5,7) -> (8,9) -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

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

int compare(const void *a, const void *b) {
    Activity *act1 = (Activity *)a;
    Activity *act2 = (Activity *)b;
    return act1->finish - act2->finish; // sort by finish time
}

void activitySelection(Activity activities[], int n) {
    qsort(activities, n, sizeof(Activity), compare); // sort activities by finish time
    if (n == 0) return;

    printf("Selected activities: ");
    int last_finish = activities[0].finish;
    printf("(%d,%d) ", activities[0].start, activities[0].finish); // select first activity

    for (int i = 1; i < n; i++) {
        if (activities[i].start >= last_finish) { // no overlap check
            printf("-> (%d,%d) ", activities[i].start, activities[i].finish); // select activity
            last_finish = activities[i].finish; // update last finish
        }
    }
    printf("-> null\n");
}

int main() {
    Activity activities[] = {{1,4}, {3,5}, {0,6}, {5,7}, {8,9}, {5,9}};
    int n = sizeof(activities) / sizeof(activities[0]);
    activitySelection(activities, n);
    return 0;
}

qsort(activities, n, sizeof(Activity), compare);

sort activities by finish time to prioritize earliest finishing

printf("(%d,%d) ", activities[0].start, activities[0].finish);

select first activity after sorting

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

check if current activity starts after or when last selected finished

printf("-> (%d,%d) ", activities[i].start, activities[i].finish);

select current activity if no overlap

last_finish = activities[i].finish;

update last finish time to current activity's finish

Output

Selected activities: (1,4) -> (5,7) -> (8,9) -> null

Complexity Analysis

Time: O(n log n) because sorting the activities by finish time dominates the runtime

Space: O(1) because selection is done in place with no extra data structures

vs Alternative: Naive approach tries all subsets with exponential time; greedy sorting reduces it to O(n log n)

Edge Cases

No activities

No output, no activities selected

DSA C

qsort(activities, n, sizeof(Activity), compare);

All activities overlap

Only the first activity is selected

DSA C

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

Activities with same finish time

Selects the first one and skips others starting before last finish

DSA C

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

When to Use This Pattern

When asked to schedule the maximum number of non-overlapping intervals, use the greedy activity selection pattern by sorting on finish times.

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 >= last finish
Fix: Always check if current activity starts after or at the finish time of last selected activity

Summary

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

Use when you need to schedule the most tasks or events without overlap in a single resource.

Sorting by finish time and greedily picking compatible activities ensures optimal selection.

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