Activity Selection Problem in DSA C# - Execution Trace

Concept Flow - Activity Selection Problem

Sort activities by finish time

↓

Select first activity

↓

For each next activity

↓

Check if start time >= last selected finish

↓

Select activity

↓

Repeat

↓

Done

Sort activities by finish time, then pick the earliest finishing activity that doesn't overlap with previously selected ones.

Execution Sample

DSA C#

activities = [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)]
Sort by finish time
Select first activity
For each next activity:
  if start >= last finish: select
Print selected activities

Select maximum number of non-overlapping activities by sorting and greedy selection.

Execution Table

Step	Operation	Current Activity (start, finish)	Last Selected Finish	Selected Activities	Action
1	Sort activities by finish time	-	-	[]	Activities sorted: [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)] → [(1,4), (3,5), (0,6), (5,7), (5,9), (8,9)]
2	Select first activity	(1,4)	-	[(1,4)]	Selected first activity
3	Check next activity	(3,5)	4	[(1,4)]	3 < 4, skip
4	Check next activity	(0,6)	4	[(1,4)]	0 < 4, skip
5	Check next activity	(5,7)	4	[(1,4), (5,7)]	5 >= 4, select
6	Check next activity	(5,9)	7	[(1,4), (5,7)]	5 < 7, skip
7	Check next activity	(8,9)	7	[(1,4), (5,7), (8,9)]	8 >= 7, select
8	End	-	9	[(1,4), (5,7), (8,9)]	No more activities

💡 All activities checked, selection complete.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	Final
Selected Activities	[]	[(1,4)]	[(1,4), (5,7)]	[(1,4), (5,7), (8,9)]	[(1,4), (5,7), (8,9)]
Last Selected Finish	-	4	7	9	9
Current Activity	-	(1,4)	(5,7)	(8,9)	-

Key Moments - 3 Insights

Why do we sort activities by their finish time first?

Sorting by finish time ensures we always pick the activity that frees up time earliest, allowing more activities to fit later. See Step 1 in execution_table.

Why do we compare the start time of the current activity with the finish time of the last selected activity?

To avoid overlapping activities, we only select if the current activity starts after or exactly when the last selected one finishes. See Steps 3, 5, and 7.

Why do we skip activities that start before the last selected finish time?

Because they overlap with already selected activities and can't be done simultaneously. See Steps 3, 4, and 6 where activities are skipped.

Visual Quiz - 3 Questions

Look at the execution_table, what is the selected activities list after Step 5?

A [(1,4), (5,7)]

B [(1,4)]

C [(1,4), (3,5)]

D [(5,7)]

💡 Hint

Check the 'Selected Activities' column at Step 5 in execution_table.

At which step does the condition 'start >= last finish' become false for the first time?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

Look at the 'Action' column in execution_table for when an activity is skipped due to start < last finish.

If the activity (5,9) had a finish time of 6 instead of 9, how would the selection change?

A It would be selected after (5,7)

B It would be selected instead of (5,7)

C It would be selected after (1,4) and before (5,7)

D It would be skipped as before

💡 Hint

Consider the finish times and selection order in execution_table and variable_tracker.

Concept Snapshot

Activity Selection Problem:
- Sort activities by finish time.
- Select first activity.
- For each next activity, select if start >= last selected finish.
- Skip otherwise.
- Result: maximum non-overlapping activities selected.

Full Transcript

The Activity Selection Problem chooses the maximum number of activities that don't overlap. First, activities are sorted by their finish times. Then, starting with the earliest finishing activity, each next activity is checked. If its start time is equal or after the last selected activity's finish time, it is selected; otherwise, it is skipped. This greedy approach ensures the most activities fit without overlap. The execution table shows each step, the current activity checked, the last selected finish time, and the selected activities list. Key moments clarify why sorting and comparisons are done. The visual quiz tests understanding of selection steps and conditions.

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