Activity Selection Problem in DSA C# - Time & Space Complexity

Time Complexity: Activity Selection Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to pick the most activities grows as the number of activities increases.

How does the program's work change when we have more activities to choose from?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Activities sorted by finish time
int[] start = {1, 3, 0, 5, 8, 5};
int[] finish = {2, 4, 6, 7, 9, 9};

List<int> SelectActivities(int[] start, int[] finish) {
    List<int> selected = new List<int>();
    int lastFinish = 0;
    for (int i = 0; i < start.Length; i++) {
        if (start[i] >= lastFinish) {
            selected.Add(i);
            lastFinish = finish[i];
        }
    }
    return selected;
}
    

This code picks the maximum number of activities that don't overlap, assuming activities are sorted by finish time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through all activities once.
• How many times: Exactly once for each activity (n times).

How Execution Grows With Input

As the number of activities increases, the code checks each activity once to decide if it fits.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows directly with the number of activities.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line with the number of activities.

Common Mistake

[X] Wrong: "The code checks pairs of activities, so it must be O(n²)."

[OK] Correct: The code only loops once through the list, not nested loops comparing pairs, so it is linear, not quadratic.

Interview Connect

Understanding this linear time solution shows you can find efficient ways to handle scheduling problems, a common real-world task.

Self-Check

"What if the activities were not sorted by finish time? How would the time complexity change?"

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