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.