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, you always pick the one that ends soonest so the room becomes free for the next meeting quickly.

Activities sorted by finish time:
[Activity1: start=1, end=4] -> [Activity2: start=3, end=5] -> [Activity3: start=0, end=6] -> [Activity4: start=5, end=7] -> [Activity5: start=8, end=9] -> null

Dry Run Walkthrough

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

Goal: Select the maximum number of non-overlapping activities

Step 1: Sort activities by finish time

[1,4] -> [3,5] -> [0,6] -> [5,7] -> [8,9] -> null

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

Step 2: Select first activity (1,4)

[1,4]* -> [3,5] -> [0,6] -> [5,7] -> [8,9] -> null

Why: First activity always selected as it finishes earliest

Step 3: Skip (3,5) because it starts before (1,4) ends

[1,4]* -> [3,5] -> [0,6] -> [5,7] -> [8,9] -> null

Why: Overlap with previously selected activity

Step 4: Skip (0,6) because it starts before (1,4) ends

[1,4]* -> [3,5] -> [0,6] -> [5,7] -> [8,9] -> null

Why: Overlap with previously selected activity

Step 5: Select (5,7) because it starts after (1,4) ends

[1,4]* -> [3,5] -> [0,6] -> [5,7]* -> [8,9] -> null

Why: No overlap, can schedule next

Step 6: Select (8,9) because it starts after (5,7) ends

[1,4]* -> [3,5] -> [0,6] -> [5,7]* -> [8,9]* -> null

Why: No overlap, last activity fits

Result:

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Activity
{
    public int Start { get; set; }
    public int Finish { get; set; }
    public Activity(int start, int finish)
    {
        Start = start;
        Finish = finish;
    }
}

class Program
{
    static List<Activity> ActivitySelection(List<Activity> activities)
    {
        // Sort activities by finish time
        activities.Sort((a, b) => a.Finish.CompareTo(b.Finish));

        List<Activity> selected = new List<Activity>();
        int lastFinish = -1;

        foreach (var activity in activities)
        {
            // Select activity if it starts after last selected finish
            if (activity.Start >= lastFinish)
            {
                selected.Add(activity); // add to result
                lastFinish = activity.Finish; // update last finish
            }
        }
        return selected;
    }

    static void Main()
    {
        var activities = new List<Activity>
        {
            new Activity(1,4),
            new Activity(3,5),
            new Activity(0,6),
            new Activity(5,7),
            new Activity(8,9)
        };

        var result = ActivitySelection(activities);

        foreach (var act in result)
        {
            Console.WriteLine($"({act.Start},{act.Finish})");
        }
    }
}

activities.Sort((a, b) => a.Finish.CompareTo(b.Finish));

sort activities by their finish time ascending

if (activity.Start >= lastFinish)

check if current activity starts after last selected activity finished

selected.Add(activity);

select current activity as it does not overlap

lastFinish = activity.Finish;

update last finish time to current activity's finish

Output

(1,4)

(5,7)

(8,9)

Complexity Analysis

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

Space: O(n) because we store the selected activities in a list

vs Alternative: Compared to checking all subsets (exponential), this greedy approach is efficient and optimal

Edge Cases

empty list of activities

returns empty selection without error

DSA C#

activities.Sort((a, b) => a.Finish.CompareTo(b.Finish));

all activities overlap completely

only one activity is selected, the one finishing earliest

DSA C#

if (activity.Start >= lastFinish)

activities with same finish time

selects the first one encountered, others skipped if overlapping

DSA C#

activities.Sort((a, b) => a.Finish.CompareTo(b.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 activities that overlap with previously selected ones
Fix: Always check if the current activity starts after or exactly when the last selected activity finishes

Summary

Selects the maximum number of activities that don't overlap by always choosing the earliest finishing activity next.

Use when you want to schedule as many non-overlapping intervals as possible.

The key insight is sorting activities by finish time lets you greedily pick the best next activity.

Practice

1. What is the main goal of the Activity Selection Problem?

easy

A. Select the maximum number of activities that don't overlap in time

B. Find the activity with the longest duration

C. Sort activities by their start time

D. Calculate the total duration of all activities

Solution

1. Step 1: Understand the problem goal

   The Activity Selection Problem aims to choose activities that do not overlap and maximize the count.

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 A

4. Quick Check:

   Goal = Max non-overlapping activities [OK]

Hint: Focus on maximizing count without time conflicts [OK]

Common Mistakes:

• Confusing longest duration with maximum count
• Sorting by start time only
• Summing durations instead of counting activities

2. Which of the following C# code snippets correctly sorts activities by their finish time for the Activity Selection Problem?

easy

A. activities.Sort((a, b) => a.Start.CompareTo(b.Start));

B. activities.Sort((a, b) => a.Finish.CompareTo(b.Finish));

C. activities.OrderBy(a => a.Duration);

D. activities.OrderByDescending(a => a.Start);

Solution

1. Step 1: Identify sorting criteria for Activity Selection

   The greedy approach requires sorting activities by their finish time in ascending order.

2. Step 2: Match code with sorting by finish time

   activities.Sort((a, b) => a.Finish.CompareTo(b.Finish)); uses Sort with finish time comparison, which is correct.

3. Final Answer:

   activities.Sort((a, b) => a.Finish.CompareTo(b.Finish)); -> Option B

4. Quick Check:

   Sort by finish time = activities.Sort((a, b) => a.Finish.CompareTo(b.Finish)); [OK]

Hint: Sort activities by finish time ascending [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Using OrderBy without assignment
• Sorting descending instead of ascending

3. Given the following activities with start and finish times:
var activities = new List<Activity> { new Activity(1, 4), new Activity(3, 5), new Activity(0, 6), new Activity(5, 7), new Activity(8, 9) };
What is the maximum number of non-overlapping activities selected by the greedy algorithm?

medium

A. 5

B. 4

C. 2

D. 3

Solution

1. Step 1: Sort activities by finish time

   Sorted activities by finish time: (1,4), (3,5), (0,6), (5,7), (8,9)

2. Step 2: Select activities greedily

   Select (1,4) first, skip (3,5) and (0,6) because they overlap, select (5,7), then (8,9). Total selected = 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Max non-overlapping = 3 [OK]

Hint: Pick earliest finishing activities first [OK]

Common Mistakes:

• Counting overlapping activities
• Not sorting by finish time
• Selecting activities by start time only

4. Consider this buggy C# code for Activity Selection:

activities.Sort((a, b) => a.Start.CompareTo(b.Start));
var selected = new List<Activity>();
selected.Add(activities[0]);
foreach(var act in activities) {
  if(act.Start >= selected.Last().Finish) {
    selected.Add(act);
  }
}

What is the main error causing incorrect results?

medium

A. Looping over activities incorrectly

B. Using >= instead of > in condition

C. Sorting by start time instead of finish time

D. Not initializing selected list before adding

Solution

1. Step 1: Check sorting criteria

   The code sorts activities by start time, but greedy algorithm requires sorting by finish time.

2. Step 2: Understand impact of wrong sorting

   Sorting by start time can select overlapping activities, causing incorrect results.

3. Final Answer:

   Sorting by start time instead of finish time -> Option C

4. Quick Check:

   Sort by finish time needed, not start time [OK]

Hint: Always sort by finish time for correct selection [OK]

Common Mistakes:

• Sorting by start time
• Confusing condition operators
• Forgetting to add first activity

5. You have activities with start and finish times:
[(1,3), (2,5), (4,7), (6,9), (8,10), (9,11)]
Using the Activity Selection Problem approach, which set of activities maximizes the number of non-overlapping activities?

hard

A. [(1,3), (4,7), (8,10)]

B. [(1,3), (4,7), (6,9), (9,11)]

C. [(1,3), (6,9), (9,11)]

D. [(2,5), (6,9), (9,11)]

Solution

1. Step 1: Sort activities by finish time

   Sorted by finish time: (1,3), (2,5), (4,7), (6,9), (8,10), (9,11)

2. Step 2: Select activities greedily

   Select (1,3), skip (2,5) because it overlaps with (1,3), select (4,7) (4 >= 3), select (6,9) overlaps with (4,7)? No, 6 < 7 so skip (6,9), select (8,10) (8 >= 7), select (9,11) overlaps with (8,10)? 9 < 10 so skip (9,11). But this conflicts with options, so let's re-check carefully.

3. Step 2 corrected:

   Select (1,3), skip (2,5), select (4,7), skip (6,9) (6 < 7), select (8,10), skip (9,11) (9 < 10). Total 3 activities: (1,3), (4,7), (8,10).

4. Step 3: Verify options

   [(1,3), (4,7), (8,10)] matches the selected activities: [(1,3), (4,7), (8,10)].

5. Final Answer:

   [(1,3), (4,7), (8,10)] -> Option A

6. Quick Check:

   Greedy selection = [(1,3), (4,7), (8,10)] [OK]

Hint: Pick earliest finishing compatible activities stepwise [OK]

Common Mistakes:

• Choosing overlapping activities
• Ignoring sorting by finish time
• Selecting more activities that overlap