Activity Selection Problem in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Activity Selection Greedy Algorithm

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

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        List<int> selected = ActivitySelection(start, finish);
        Console.WriteLine(string.Join(" -> ", selected) + " -> null");
    }

    static List<int> ActivitySelection(int[] start, int[] finish) {
        List<int> result = new List<int>();
        int n = start.Length;
        int i = 0;
        result.Add(i);
        for (int j = 1; j < n; j++) {
            if (start[j] >= finish[i]) {
                result.Add(j);
                i = j;
            }
        }
        return result;
    }
}

A 1 -> 3 -> 4 -> null

B 0 -> 1 -> 4 -> null

C 0 -> 2 -> 3 -> 5 -> null

D 0 -> 1 -> 3 -> 4 -> null

💡 Hint

Trace the selection by comparing start times with the last selected finish time.

The algorithm selects activities by earliest finish time. It starts with activity 0, then picks activity 1 (start 3 >= finish 2), then activity 3 (start 5 >= finish 4), then activity 4 (start 8 >= finish 7). So the selected activities are 0, 1, 3, 4.

🧠 Conceptual

intermediate

Understanding Activity Selection Problem

Which of the following best describes the main goal of the Activity Selection Problem?

A To minimize the total time spent on activities.

B To select the maximum number of activities that do not overlap in time.

C To schedule all activities regardless of overlap.

D To find the activity with the longest duration.

💡 Hint

Think about how many activities can be done without conflicts.

The Activity Selection Problem aims to choose the largest set of activities that do not overlap, maximizing the number of activities one can attend.

🔧 Debug

advanced

Identify the Error in Activity Selection Code

What error will the following code produce when run?

DSA C#

int[] start = {1, 3, 0, 5, 8, 5};
int[] finish = {2, 4, 6, 7};
List<int> selected = ActivitySelection(start, finish);

List<int> ActivitySelection(int[] start, int[] finish) {
    List<int> result = new List<int>();
    int n = start.Length;
    int i = 0;
    result.Add(i);
    for (int j = 1; j < n; j++) {
        if (start[j] >= finish[i]) {
            result.Add(j);
            i = j;
        }
    }
    return result;
}

A IndexOutOfRangeException

B NullReferenceException

C No error, outputs selected activities

D InvalidOperationException

💡 Hint

Check if both arrays have the same length.

The finish array has fewer elements than the start array. Accessing finish[i] when i reaches 4 causes IndexOutOfRangeException.

🚀 Application

advanced

Maximum Activities Count

Given start times [2, 1, 3, 0, 5, 8] and finish times [3, 2, 4, 6, 7, 9], what is the maximum number of non-overlapping activities that can be selected?

A 5

B 3

C 4

D 6

💡 Hint

Sort activities by finish time and select greedily.

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

❓ Predict Output

expert

Output of Activity Selection with Unsorted Input

What is the output of this C# code that attempts to select activities without sorting by finish time?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] start = {4, 1, 3, 0, 5, 8};
        int[] finish = {5, 2, 4, 6, 7, 9};
        List<int> selected = ActivitySelection(start, finish);
        Console.WriteLine(string.Join(" -> ", selected) + " -> null");
    }

    static List<int> ActivitySelection(int[] start, int[] finish) {
        List<int> result = new List<int>();
        int n = start.Length;
        int i = 0;
        result.Add(i);
        for (int j = 1; j < n; j++) {
            if (start[j] >= finish[i]) {
                result.Add(j);
                i = j;
            }
        }
        return result;
    }
}

A 1 -> 3 -> 5 -> null

B 1 -> 2 -> 4 -> 5 -> null

C 0 -> 4 -> 5 -> null

D 0 -> 2 -> 4 -> null

💡 Hint

Without sorting by finish time, the greedy approach may select fewer activities.

The code selects activity 0 (start 4, finish 5), then activity 4 (start 5 >= 5), then activity 5 (start 8 >= 7). So selected are 0, 4, 5.

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