Activity Selection Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Activity Selection

What is the output of the following C code that selects the maximum number of non-overlapping activities?

DSA C

#include <stdio.h>

void printMaxActivities(int start[], int finish[], int n) {
    int i, j;
    printf("Selected activities: ");
    i = 0;
    printf("%d ", i);
    for (j = 1; j < n; j++) {
        if (start[j] >= finish[i]) {
            printf("%d ", j);
            i = j;
        }
    }
    printf("\n");
}

int main() {
    int start[] = {1, 3, 0, 5, 8, 5};
    int finish[] = {2, 4, 6, 7, 9, 9};
    int n = sizeof(start)/sizeof(start[0]);
    printMaxActivities(start, finish, n);
    return 0;
}

A Selected activities: 0 1 3 4

B Selected activities: 0 2 3 5

C Selected activities: 1 3 4

D Selected activities: 0 1 4

💡 Hint

Remember the greedy approach selects the first activity and then picks the next activity whose start time is greater or equal to the finish time of the last selected activity.

The code selects activities by iterating through the list and choosing the next activity that starts after or when the last selected activity finishes. The selected indices are 0, 1, 3, and 4.

🧠 Conceptual

intermediate

Key Idea Behind Activity Selection Problem

What is the main idea behind the greedy solution to the Activity Selection Problem?

A Always select the activity with the earliest start time.

B Always select the activity with the shortest duration.

C Always select the activity that starts latest among the remaining activities.

D Always select the activity that finishes earliest among the remaining activities.

💡 Hint

Think about which choice leaves the most room for other activities.

Selecting the activity that finishes earliest allows more activities to fit after it, maximizing the total number of activities selected.

🔧 Debug

advanced

Identify the Bug in Activity Selection Code

What error will the following code produce when run?

DSA C

#include <stdio.h>

void printMaxActivities(int start[], int finish[], int n) {
    int i = 0, j;
    printf("Selected activities: %d ", i);
    for (j = 1; j < n; j++) {
        if (start[j] >= finish[i]) {
            printf("%d ", j);
            i = j;
        }
    }
    printf("\n");
}

int main() {
    int start[] = {1, 3, 0, 5, 8, 5};
    int finish[] = {2, 4, 6, 7, 9, 9};
    int n = sizeof(start)/sizeof(start[0]);
    printMaxActivities(start, finish, n);
    return 0;
}

A Runs correctly and prints selected activities.

B Segmentation fault due to out-of-bounds array access.

C Compilation error due to missing semicolon.

D Logical error: prints wrong activities but no crash.

💡 Hint

Check the loop condition and array indexing carefully.

The loop runs with j <= n, which causes j to reach n, an invalid index for arrays of size n (0-based indexing). This leads to out-of-bounds access and segmentation fault.

🚀 Application

advanced

Maximum Number of Activities Selected

Given the start times [2, 1, 3, 0, 5, 8] and finish times [3, 2, 4, 6, 7, 9], how many activities can be selected without overlapping?

A 4

B 3

C 5

D 6

💡 Hint

Sort activities by finish time and pick greedily.

Sorted by finish time: activities with finish times 2,3,4,6,7,9. Selecting activities 1,0,2,4 gives 4 activities without overlap.

🧠 Conceptual

expert

Why Sorting by Finish Time is Crucial?

Why is sorting activities by their finish times essential in the greedy solution to the Activity Selection Problem?

A It ensures the earliest starting activities are chosen first.

B It simplifies the code but does not affect the correctness of the solution.

C It guarantees the maximum number of activities can be selected by always choosing the earliest finishing activity.

D It helps to select activities with the longest duration first.

💡 Hint

Think about how finish times affect the possibility of scheduling more activities.

Sorting by finish time allows the algorithm to pick the activity that leaves the most room for others, ensuring the maximum number of activities are selected.

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