Activity Selection Problem in DSA Rust - Execution Trace

Concept Flow - Activity Selection Problem

Sort activities by finish time

↓

Select first activity

↓

For each next activity

↓

If start time >= last selected finish

↓

Select activity

↓

Repeat until all activities checked

↓

Return selected activities

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

Execution Sample

DSA Rust

let activities = [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)];
let selected = activity_selection(&activities);
println!("Selected: {:?}", selected);

Selects the maximum number of non-overlapping activities from a list of (start, finish) times.

Execution Table

Step	Operation	Current Activity (start, finish)	Last Selected Finish	Selected Activities	Visual State
1	Sort activities by finish time	[(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)]	-	[]	[(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)] sorted to [(1,4), (3,5), (0,6), (5,7), (5,9), (8,9)]
2	Select first activity	(1,4)	-	[(1,4)]	Selected first activity (1,4)
3	Check next activity	(3,5)	4	[(1,4)]	3 < 4 (start < last finish), skip (3,5)
4	Check next activity	(0,6)	4	[(1,4)]	0 < 4, skip (0,6)
5	Check next activity	(5,7)	4	[(1,4), (5,7)]	5 >= 4, select (5,7)
6	Check next activity	(5,9)	7	[(1,4), (5,7)]	5 < 7, skip (5,9)
7	Check next activity	(8,9)	7	[(1,4), (5,7), (8,9)]	8 >= 7, select (8,9)
8	End	-	9	[(1,4), (5,7), (8,9)]	All activities checked, done

💡 All activities checked, no more to select

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_finish	-	4	7	9	9
current_activity	-	(1,4)	(5,7)	(8,9)	-

Key Moments - 3 Insights

Why do we sort activities by 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 skip activities that start before last selected finish time?

Because they overlap with the last selected activity and can't be done together. See Steps 3 and 4 where activities starting before 4 are skipped.

Why do we select the first activity without checking?

Because after sorting, the first activity finishes earliest, so it's always safe to pick it first. See Step 2 in execution_table.

Visual Quiz - 3 Questions

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

A [(1,4), (0,6)]

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

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

D [(5,7)]

💡 Hint

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

At which step does the algorithm select the activity (8,9)?

A Step 4

B Step 7

C Step 6

D Step 3

💡 Hint

Look for (8,9) in the 'Current Activity' and 'Selected Activities' columns in execution_table.

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

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

B It would still be skipped

C It would be selected after (5,7)

D It would be selected before (1,4)

💡 Hint

Changing finish to 6 places (5,6) earlier in sorted list (after (0,6)), selected since 5 >= 4 (last_finish after (1,4)), then last_finish=6 skips (5,7).

Concept Snapshot

Activity Selection Problem:
- Sort activities by finish time
- Select first activity
- For each next activity, if start >= last selected finish, select it
- Repeat until all checked
- Result: max non-overlapping activities

Full Transcript

The Activity Selection Problem finds the maximum number of activities that don't overlap. First, activities are sorted by their finish times. Then, the earliest finishing activity is selected. For each next activity, if its start time is at or after the last selected activity's finish time, it is selected. This process continues until all activities are checked. The output is the list of selected activities that fit without overlapping.

Practice

1. What is the main goal of the Activity Selection Problem?

easy

A. Calculate the total duration of all activities

B. Select the maximum number of activities that don't overlap in time

C. Sort activities by their start time

D. Find the activity with the longest duration

Solution

1. Step 1: Understand the problem objective

   The Activity Selection Problem aims to choose the largest set of activities that do not overlap in their time intervals.

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 B

4. Quick Check:

   Goal = Max non-overlapping activities [OK]

Hint: Focus on maximizing non-overlapping activities [OK]

Common Mistakes:

• Confusing longest duration with maximum count
• Sorting by start time only
• Summing durations instead of counting activities

2. Which Rust code snippet correctly sorts a vector of activities by their finish time? Assume each activity is a tuple (start: i32, finish: i32).

easy

A. activities.sort_by_key(|a| a.1);

B. activities.sort_by_key(|a| a.0);

C. activities.sort_unstable_by(|a, b| b.1.cmp(&a.1));

D. activities.sort_by(|a, b| a.0.cmp(&b.0));

Solution

1. Step 1: Identify sorting key for finish time

   Each activity is a tuple (start, finish). The finish time is at index 1.

2. Step 2: Choose correct sorting method

   Sorting by finish time ascending uses sort_by_key(|a| a.1). activities.sort_by_key(|a| a.1); matches this.

3. Final Answer:

   activities.sort_by_key(|a| a.1); -> Option A

4. Quick Check:

   Sort by finish time = a.1 [OK]

Hint: Sort activities by finish time using .sort_by_key(|a| a.1) [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Sorting in descending order incorrectly
• Using unstable sort unnecessarily

3. What is the output of the following Rust code that implements the activity selection logic?

let mut activities = vec![(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)];
activities.sort_by_key(|a| a.1);
let mut selected = vec![activities[0]];
let mut last_finish = activities[0].1;
for &activity in &activities[1..] {
    if activity.0 >= last_finish {
        selected.push(activity);
        last_finish = activity.1;
    }
}
println!("{:?}", selected);

medium

A. [(1, 4), (3, 5), (5, 7), (8, 9)]

B. [(0, 6), (5, 7), (8, 9)]

C. [(1, 4), (5, 7), (8, 9)]

D. [(1, 4), (5, 9)]

Solution

1. Step 1: Sort activities by finish time

   Sorted activities: [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)]

2. Step 2: Select activities greedily

   Start with (1,4). Next, (3,5) starts before 4, skip. (0,6) starts before 4, skip. (5,7) starts at 5 ≥ 4, select. (8,9) starts at 8 ≥ 7, select. (5,9) starts at 5 < 7, skip.

3. Final Answer:

   [(1, 4), (5, 7), (8, 9)] -> Option C

4. Quick Check:

   Greedy selection = [(1,4),(5,7),(8,9)] [OK]

Hint: Pick earliest finishing activities that start after last finish [OK]

Common Mistakes:

• Selecting overlapping activities
• Not sorting by finish time first
• Including activities starting before last finish

4. Identify the bug in this Rust code snippet for the Activity Selection Problem:

let mut activities = vec![(1, 3), (2, 5), (4, 7)];
activities.sort_by_key(|a| a.0);
let mut selected = vec![activities[0]];
let mut last_finish = activities[0].1;
for &activity in &activities[1..] {
    if activity.0 > last_finish {
        selected.push(activity);
        last_finish = activity.1;
    }
}
println!("{:?}", selected);

medium

A. Using > instead of >= in the if condition

B. Not pushing the first activity into selected

C. Not initializing last_finish correctly

D. Sorting by start time instead of finish time

Solution

1. Step 1: Check sorting criteria

   The code sorts activities by start time (a.0), but the greedy approach requires sorting by finish time.

2. Step 2: Understand impact of sorting

   Sorting by start time breaks the greedy logic, causing incorrect selection of activities.

3. Final Answer:

   Sorting by start time instead of finish time -> Option D

4. Quick Check:

   Sort by finish time needed, not start time [OK]

Hint: Always sort activities by finish time, not start time [OK]

Common Mistakes:

• Sorting by start time
• Using strict > instead of >= (less critical)
• Incorrect initialization of last_finish

5. Given a list of activities with start and finish times, how would you modify the standard Activity Selection Problem to select activities that maximize total duration instead of count? Which approach is correct?

hard

A. Use dynamic programming to consider all subsets and maximize total duration

B. Sort activities by start time and greedily pick those with longest duration

C. Sort by finish time and pick activities with shortest duration first

D. Select activities randomly and check total duration

Solution

1. Step 1: Understand difference in optimization goal

   Maximizing total duration is different from maximizing count; greedy approach fails here.

2. Step 2: Choose correct algorithmic approach

   Dynamic programming can consider all subsets to find the maximum total duration without overlaps.

3. Final Answer:

   Use dynamic programming to consider all subsets and maximize total duration -> Option A

4. Quick Check:

   Max total duration needs DP, not greedy [OK]

Hint: Max duration needs DP, not greedy selection [OK]

Common Mistakes:

• Trying greedy for max duration
• Sorting by start time only
• Random selection without logic