Activity Selection Problem in DSA C - Deep Dive

Overview - Activity Selection Problem

What is it?

The Activity Selection Problem is about choosing the maximum number of activities that don't overlap in time. Each activity has a start time and an end time. The goal is to select as many activities as possible so that no two chosen activities happen at the same time. This helps in scheduling tasks efficiently.

Why it matters

Without this concept, scheduling tasks or events would be inefficient, leading to wasted time or resources. For example, if you book overlapping meetings, you can't attend all of them. The Activity Selection Problem helps find the best way to fit in the most activities without conflicts, which is useful in real life for planning, resource management, and time optimization.

Where it fits

Before learning this, you should understand arrays and sorting basics. After this, you can explore greedy algorithms more deeply and study interval scheduling problems or dynamic programming approaches for related scheduling challenges.

Mental Model

Core Idea

Pick activities that finish earliest to leave room for more activities later.

Think of it like...

Imagine you have a single meeting room and many people want to use it. To fit the most meetings, you always let the meeting that ends soonest happen first, then pick the next meeting that starts after it ends, and so on.

Activities sorted by finish time:
┌─────────────┐
│ Activity 1  │ Start: 1, End: 4
│ Activity 2  │ Start: 3, End: 5
│ Activity 3  │ Start: 0, End: 6
│ Activity 4  │ Start: 5, End: 7
│ Activity 5  │ Start: 8, End: 9
└─────────────┘
Selection process:
[Activity 1 (ends at 4)] -> [Activity 4 (starts at 5)] -> [Activity 5 (starts at 8)]

Build-Up - 7 Steps

1

Foundation

Understanding Activities and Time Slots

Concept: Activities have start and end times that define when they happen.

Each activity is represented by two numbers: start time and end time. For example, an activity starting at 1 and ending at 4 means it occupies the time from 1 up to but not including 4. Activities can overlap if their times intersect.

Result

You can list activities with their start and end times and see which overlap.

Knowing how activities are represented is essential to understand when they conflict and cannot be scheduled together.

2

Foundation

Sorting Activities by Finish Time

Concept: Sorting activities by their end times helps in making optimal choices.

Given a list of activities, sort them so the one that finishes earliest comes first. This order helps us pick activities that free up time for others.

Result

Activities ordered from earliest finish to latest finish.

Sorting by finish time sets the stage for a simple rule to select the maximum number of non-overlapping activities.

3

Intermediate

Greedy Selection of Activities

🤔Before reading on: do you think picking the longest activity first or the earliest finishing activity first leads to more total activities? Commit to your answer.

Concept: Choosing the earliest finishing activity first allows more activities to fit afterward.

Start by selecting the activity that finishes first. Then, skip all activities that start before this one ends. Repeat by selecting the next activity that starts after the last selected one ends.

Result

A list of selected activities with no overlaps and maximum count.

Understanding that picking the earliest finishing activity leaves the most room for others is the key to the greedy solution.

4

Intermediate

Implementing the Algorithm in C

🤔Before reading on: do you think a simple loop checking start and end times is enough to select activities? Commit to your answer.

Concept: A loop can iterate through sorted activities and pick compatible ones.

Sort activities by finish time. Initialize the first activity as selected. For each next activity, if its start time is after or equal to the last selected activity's end time, select it. Continue until all activities are checked. Example code snippet: #include #include typedef struct { int start; int end; } Activity; int compare(const void *a, const void *b) { Activity *act1 = (Activity *)a; Activity *act2 = (Activity *)b; return act1->end - act2->end; } void selectActivities(Activity activities[], int n) { qsort(activities, n, sizeof(Activity), compare); int last_end = activities[0].end; printf("Selected activities:\n"); printf("(%d, %d)\n", activities[0].start, activities[0].end); for (int i = 1; i < n; i++) { if (activities[i].start >= last_end) { printf("(%d, %d)\n", activities[i].start, activities[i].end); last_end = activities[i].end; } } } int main() { Activity activities[] = {{1,4}, {3,5}, {0,6}, {5,7}, {8,9}, {5,9}}; int n = sizeof(activities)/sizeof(activities[0]); selectActivities(activities, n); return 0; }

Result

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

Seeing the algorithm in code clarifies how sorting and selection work together to solve the problem efficiently.

5

Intermediate

Time Complexity and Efficiency

Concept: The algorithm runs efficiently due to sorting and a single pass selection.

Sorting the activities takes O(n log n) time. Selecting activities in one pass takes O(n). Overall, the algorithm runs in O(n log n) time, which is efficient for large inputs.

Result

You understand the algorithm is fast and scalable.

Knowing the time complexity helps you trust the algorithm for real-world large scheduling problems.

6

Advanced

Handling Edge Cases and Equal Finish Times

🤔Before reading on: do you think activities with the same finish time can both be selected? Commit to your answer.

Concept: When activities finish at the same time, only one can be selected if they overlap.

If two activities end at the same time, the one that starts earlier or later may affect selection. The algorithm picks the first in sorted order. To handle ties, stable sorting or additional rules can be applied. Also, activities with zero length or invalid times should be handled carefully.

Result

Robust selection that handles ties and unusual inputs correctly.

Understanding edge cases prevents bugs and ensures the algorithm works correctly in all scenarios.

7

Expert

Extending to Weighted Activity Selection

🤔Before reading on: do you think the greedy approach works if activities have different values or weights? Commit to your answer.

Concept: When activities have weights, the problem requires dynamic programming instead of greedy.

If each activity has a value or weight, the goal changes to maximizing total value, not count. The greedy method fails here. Instead, use dynamic programming to consider combinations of activities and their weights. This is called the Weighted Interval Scheduling Problem.

Result

You know when greedy fails and how to approach the weighted version.

Recognizing the limits of greedy algorithms and knowing the switch to dynamic programming is crucial for advanced scheduling problems.

Under the Hood

The algorithm works by first sorting activities by their finish times. This ordering ensures that when we pick the earliest finishing activity, we leave the maximum possible time for the remaining activities. Then, a single pass through the sorted list selects activities that start after the last selected activity ends. This greedy choice is locally optimal and leads to a globally optimal solution because of the problem's structure.

Why designed this way?

The problem was designed to be solved greedily because the earliest finishing activity frees up time for more activities. Alternatives like trying all combinations would be too slow. The greedy approach was chosen for its simplicity and efficiency, exploiting the problem's optimal substructure and greedy-choice property.

Sorted activities by finish time:
┌─────────────┐
│ Activity 1  │
│ Start: 1    │
│ End: 4      │
├─────────────┤
│ Activity 2  │
│ Start: 3    │
│ End: 5      │
├─────────────┤
│ Activity 4  │
│ Start: 5    │
│ End: 7      │
├─────────────┤
│ Activity 5  │
│ Start: 8    │
│ End: 9      │
└─────────────┘

Selection flow:
[Activity 1] -> [Activity 4] -> [Activity 5]

Each arrow means the next activity starts after the previous ends.

Myth Busters - 3 Common Misconceptions

Quick: Does picking the longest activity first always maximize the number of activities? Commit yes or no.

Common Belief: Picking the longest activity first will maximize the total scheduled time and number of activities.

Reality: Picking the longest activity first often reduces the number of activities you can schedule because it blocks more time, leaving less room for others.

Why it matters: Choosing the longest activity first can lead to fewer total activities scheduled, wasting opportunities to fit more tasks.

Quick: Can you select overlapping activities if they start exactly when another ends? Commit yes or no.

Common Belief: Activities that start exactly when another ends overlap and cannot both be selected.

Reality: Activities that start at the exact time another ends do not overlap and can both be selected.

Why it matters: Misunderstanding this causes missing valid activities and reduces the total count unnecessarily.

Quick: Does the greedy approach work for weighted activities? Commit yes or no.

Common Belief: The greedy method for earliest finish time also works when activities have different weights or values.

Reality: The greedy approach fails for weighted activities; dynamic programming is needed to maximize total weight.

Why it matters: Using greedy in weighted cases leads to suboptimal schedules and lost value.

Expert Zone

1

The greedy choice property holds because selecting the earliest finishing activity never blocks a better future choice.

2

Stable sorting can affect which activities are chosen when finish times tie, impacting reproducibility.

3

The problem's optimal substructure means solutions to subproblems combine to solve the whole, enabling efficient algorithms.

When NOT to use

Do not use the greedy approach when activities have weights or values; instead, use dynamic programming for the Weighted Interval Scheduling Problem. Also, if activities can be preempted or partially scheduled, other algorithms are needed.

Production Patterns

In real systems, this problem appears in CPU job scheduling, booking systems, and event planning. Often, the greedy algorithm is implemented with efficient sorting and selection loops, sometimes extended with priority queues or segment trees for dynamic updates.

Connections

Greedy Algorithms

The Activity Selection Problem is a classic example of a greedy algorithm.

Understanding this problem helps grasp the greedy strategy of making locally optimal choices to achieve a global optimum.

Dynamic Programming

Weighted Activity Selection requires dynamic programming instead of greedy.

Knowing when greedy fails and dynamic programming is needed deepens understanding of algorithm design techniques.

Project Management

Scheduling tasks without overlap is a core challenge in project management.

Learning this problem improves skills in real-world resource allocation and time management.

Common Pitfalls

#1 Selecting activities without sorting by finish time.

Wrong approach:

for (int i = 0; i < n; i++) {
if (activities[i].start >= last_end) {
select activity i;
last_end = activities[i].end;
}
}
// No sorting before this loop

Correct approach:

qsort(activities, n, sizeof(Activity), compare);
for (int i = 0; i < n; i++) {
if (activities[i].start >= last_end) {
select activity i;
last_end = activities[i].end;
}
}

Root cause:

Without sorting, the selection does not consider earliest finishing activities first, leading to suboptimal results.

#2 Treating activities that start exactly when another ends as overlapping.

Wrong approach:

if (activities[i].start > last_end) {
select activity i;
last_end = activities[i].end;
}

Correct approach:

if (activities[i].start >= last_end) {
select activity i;
last_end = activities[i].end;
}

Root cause:

Using strict greater than excludes valid activities that start right after the previous ends.

#3 Using greedy approach for weighted activities.

Wrong approach:

Sort activities by finish time and pick earliest finishing regardless of weight to maximize total value.

Correct approach:

Use dynamic programming to consider weights and find the maximum total value schedule.

Root cause:

Greedy ignores weights and can miss better combinations, so it fails for weighted problems.

Key Takeaways

The Activity Selection Problem finds the maximum number of non-overlapping activities by always picking the earliest finishing activity first.

Sorting activities by their finish times is essential to apply the greedy selection correctly and efficiently.

The greedy algorithm runs in O(n log n) time due to sorting and a single pass selection, making it practical for large inputs.

Activities that start exactly when another ends do not overlap and can both be selected.

For weighted activities, the greedy approach fails and dynamic programming is required to maximize total value.

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