Activity Selection Problem in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort activities by their finish time.

DSA C#

activities.Sort((a, b) => a.[1] - b.[1]);

Drag options to blanks, or click blank then click option'

Afinish

Bstart

Cduration

Dindex

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by start time instead of finish time.

Using duration which is not directly helpful here.

Sorting activities by their finish time helps select the maximum number of non-overlapping activities.

2fill in blank

medium

Complete the code to select the first activity after sorting.

DSA C#

selectedActivities.Add(activities[[1]]);

Drag options to blanks, or click blank then click option'

A1

B0

Cactivities.Count - 1

Dactivities.Count

Attempts:

3 left

💡 Hint

Common Mistakes

Starting selection from index 1 instead of 0.

Using activities.Count which is out of range.

The first activity in the sorted list is always selected first.

3fill in blank

hard

Fix the error in the condition to check if the next activity can be selected.

DSA C#

if (activities[i].start >= [1].finish)

Drag options to blanks, or click blank then click option'

AselectedActivities[0]

Bactivities[i-1]

CselectedActivities.Last()

Dactivities[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with activities[i-1] which may not be selected.

Using selectedActivities[0] which is the first selected, not the last.

We compare the start time of the current activity with the finish time of the last selected activity.

4fill in blank

hard

Fill both blanks to complete the loop that selects compatible activities.

DSA C#

for (int i = [1]; i < activities.Count; i++) {
    if (activities[i].start >= selectedActivities.[2]().finish) {
        selectedActivities.Add(activities[i]);
    }
}

Drag options to blanks, or click blank then click option'

A1

B0

CLast

DFirst

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop at 0 causing duplicate selection.

Using First() instead of Last() for comparison.

Start loop from 1 because first activity is already selected; check start time against last selected activity's finish time.

5fill in blank

hard

Fill all three blanks to create a dictionary of selected activities with their start times as keys.

DSA C#

var result = new Dictionary<int, Activity>() {
    { [1], [2] }
};

foreach (var act in selectedActivities) {
    result[act.[3]] = act;
}

Drag options to blanks, or click blank then click option'

AselectedActivities[0].start

BselectedActivities[0]

Cstart

Dfinish

Attempts:

3 left

💡 Hint

Common Mistakes

Using finish time as dictionary key which may cause conflicts.

Not initializing dictionary properly before adding activities.

Initialize dictionary with first selected activity's start time as key and activity as value; then add others using start time as key.

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