Activity Selection Problem in DSA C# - Build from Scratch

Activity Selection Problem

📖 Scenario: You are organizing a conference with multiple talks. Each talk has a start time and an end time. You want to select the maximum number of talks that do not overlap so attendees can attend as many talks as possible.

🎯 Goal: Build a program that selects the maximum number of non-overlapping activities from a given list of activities with start and end times.

📋 What You'll Learn

Create a list of activities with exact start and end times.

Add a variable to store the last selected activity's end time.

Use a loop to select activities that start after the last selected activity ends.

Print the selected activities in order.

💡 Why This Matters

🌍 Real World

Scheduling talks, meetings, or tasks to maximize usage of time without conflicts.

💼 Career

Useful for roles in project management, event planning, and software development involving scheduling algorithms.

1

Create the list of activities

Create a list called activities of tuples with these exact values: (1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9).

DSA C#

# Create the list of activities with start and end times
// Your code here

Hint

Use List<(int, int)> and add the exact tuples inside curly braces.

2

Add a variable to track the end time of the last selected activity

Add an integer variable called lastEndTime and set it to 0 to track the end time of the last selected activity.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List activities = new List
        {
            (1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)
        };
        // Add lastEndTime variable here
        // Your code here
    }
}

Hint

Declare int lastEndTime = 0; after the activities list.

3

Select the maximum number of non-overlapping activities

Sort the activities list by the end time. Then create a list called selectedActivities to store chosen activities. Use a foreach loop with variable activity to iterate over activities. Inside the loop, if activity.start is greater than or equal to lastEndTime, add activity to selectedActivities and update lastEndTime to activity.end.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List activities = new List
        {
            (1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)
        };
        int lastEndTime = 0;
        // Sort activities by end time
        // Create selectedActivities list
        // Use foreach loop to select activities
        // Your code here
    }
}

Hint

Use OrderBy to sort, then loop with foreach (var activity in activities) and select activities that start after lastEndTime.

4

Print the selected activities

Use a foreach loop with variable activity to iterate over selectedActivities. Inside the loop, print each activity's start and end times in the format: Start: {activity.start}, End: {activity.end}.

DSA C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List activities = new List
        {
            (1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)
        };
        int lastEndTime = 0;
        activities = activities.OrderBy(a => a.end).ToList();
        List selectedActivities = new List();
        foreach (var activity in activities)
        {
            if (activity.start >= lastEndTime)
            {
                selectedActivities.Add(activity);
                lastEndTime = activity.end;
            }
        }
        // Print selected activities
        // Your code here
    }
}

Hint

Use Console.WriteLine($"Start: {activity.start}, End: {activity.end}") inside a foreach loop over selectedActivities.

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