Activity Selection Problem in DSA C - Build from Scratch

Activity Selection Problem

📖 Scenario: You are organizing a conference with multiple activities. Each activity has a start time and an end time. You want to select the maximum number of activities that don't overlap so attendees can participate in as many as possible.

🎯 Goal: Build a program that selects the maximum number of non-overlapping activities from a given list using the Activity Selection Problem approach.

📋 What You'll Learn

Create two arrays called start and end with exact values for activity start and end times

Create an integer variable n to hold the number of activities

Implement the activity selection logic using a for loop and select activities based on their end times

Print the count of the selected activities

💡 Why This Matters

🌍 Real World

Scheduling meetings, conference talks, or any events where time slots must not overlap to maximize participation.

💼 Career

Understanding greedy algorithms and scheduling problems is important for software engineers working on calendar apps, resource allocation, and optimization tasks.

1

Create activity start and end time arrays

Create two integer arrays called start and end with these exact values: start = {1, 3, 0, 5, 8, 5} and end = {2, 4, 6, 7, 9, 9}. Also create an integer variable n and set it to 6.

DSA C

# Your code here

Hint

Use arrays to store start and end times exactly as given. Also create an integer n for the number of activities.

2

Initialize variables for activity selection

Create an integer variable called count and set it to 1. Create an integer variable called last_selected and set it to 0 to track the last selected activity index.

DSA C

int start[] = {1, 3, 0, 5, 8, 5};
int end[] = {2, 4, 6, 7, 9, 9};
int n = 6;
# Your code here

Hint

Initialize count to 1 because the first activity is always selected. last_selected keeps track of the index of the last chosen activity.

3

Select maximum activities using a loop

Use a for loop with an integer variable i starting from 1 to n - 1. Inside the loop, check if start[i] is greater than or equal to end[last_selected]. If yes, increment count by 1 and update last_selected to i.

DSA C

int start[] = {1, 3, 0, 5, 8, 5};
int end[] = {2, 4, 6, 7, 9, 9};
int n = 6;
int count = 1;
int last_selected = 0;
// Your code here

Hint

Loop through activities starting from the second one. Select an activity if its start time is after or equal to the last selected activity's end time.

4

Print the count of selected activities

Use printf to print the value of count followed by a newline.

DSA C

int start[] = {1, 3, 0, 5, 8, 5};
int end[] = {2, 4, 6, 7, 9, 9};
int n = 6;
int count = 1;
int last_selected = 0;
for (int i = 1; i = end[last_selected]) {
        count++;
        last_selected = i;
    }
}
// Your code here

Hint

Print the total number of selected activities using printf.

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