Choose the maximum number of activities that don't overlap by always picking the earliest finishing activity first.
Analogy: Imagine you have a single meeting room and many meetings to schedule. To fit the most meetings, always pick the meeting that ends soonest so the room becomes free earlier for the next meeting.
sort activities by their finish time to prioritize earliest finishing
selected.push(activities[0].clone());
select the first activity as it finishes earliest
if activity.start >= last_finish {
check if current activity starts after last selected activity finishes
selected.push(activity.clone());
select current activity as it does not overlap
last_finish = activity.finish;
update last finish time to current activity's finish
OutputSuccess
(1,4)
(5,7)
(8,11)
(12,16)
Complexity Analysis
Time: O(n log n) because we sort the activities by finish time and then scan once
Space: O(n) because we store the selected activities in a separate list
vs Alternative: Naive approach tries all subsets with exponential time; greedy sorting reduces to O(n log n)
Edge Cases
empty activity list
returns empty selection without error
DSA Rust
if activities.is_empty() { return selected; }
all activities overlap
only the earliest finishing activity is selected
DSA Rust
if activity.start >= last_finish { ... }
activities with same finish time
selects the first one encountered, skips overlapping others
DSA Rust
activities.sort_by_key(|a| a.finish);
When to Use This Pattern
When you need to schedule the maximum number of non-overlapping intervals, use the greedy activity selection pattern by sorting on finish times.
Common Mistakes
Mistake: Sorting activities by start time instead of finish time Fix: Sort activities by their finish time to ensure earliest finishing activities are chosen first
Mistake: Selecting overlapping activities without checking start time against last finish Fix: Always check if current activity starts after or at the finish time of last selected activity
Summary
Selects the maximum number of activities that don't overlap by always choosing the earliest finishing activity next.
Use when you want to schedule as many non-overlapping intervals as possible.
The key insight is sorting by finish time lets you greedily pick activities that free up time earliest.
Practice
(1/5)
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
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.
Step 2: Identify the correct goal
Among the options, only selecting the maximum number of non-overlapping activities matches the problem's goal.
Final Answer:
Select the maximum number of activities that don't overlap in time -> Option B
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
Step 1: Identify sorting key for finish time
Each activity is a tuple (start, finish). The finish time is at index 1.
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.
Final Answer:
activities.sort_by_key(|a| a.1); -> Option A
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);
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.
Final Answer:
[(1, 4), (5, 7), (8, 9)] -> Option C
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
Step 1: Check sorting criteria
The code sorts activities by start time (a.0), but the greedy approach requires sorting by finish time.
Step 2: Understand impact of sorting
Sorting by start time breaks the greedy logic, causing incorrect selection of activities.
Final Answer:
Sorting by start time instead of finish time -> Option D
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
Step 1: Understand difference in optimization goal
Maximizing total duration is different from maximizing count; greedy approach fails here.
Step 2: Choose correct algorithmic approach
Dynamic programming can consider all subsets to find the maximum total duration without overlaps.
Final Answer:
Use dynamic programming to consider all subsets and maximize total duration -> Option A
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
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.
