Activity Selection Problem in DSA Rust - Deep Dive

Overview - Activity Selection Problem

What is it?

The Activity Selection Problem is about choosing the maximum number of activities that don't overlap in time. Each activity has a start time and an end time. The goal is to select activities so that no two chosen activities happen at the same time. This helps in planning tasks efficiently.

Why it matters

Without this problem's solution, we might waste time or resources by scheduling overlapping activities. For example, if you book two meetings at the same time, you can't attend both. Solving this problem helps in real life for scheduling, resource allocation, and time management.

Where it fits

Before learning this, you should understand arrays or lists and sorting basics. After this, you can explore more complex scheduling problems like interval partitioning or dynamic programming approaches to scheduling.

Mental Model

Core Idea

Pick activities that finish earliest to leave room for more activities later.

Think of it like...

Imagine you have a single meeting room and many people want to use it. To fit the most meetings, you always let the meeting that ends soonest happen first, then pick the next meeting that starts after it ends.

Activities sorted by finish time:
┌───────────────┐
│ Activity List │
├───────────────┤
│ A1: 1 - 4    │
│ A2: 3 - 5    │
│ A3: 0 - 6    │
│ A4: 5 - 7    │
│ A5: 8 - 9    │
│ A6: 5 - 9    │
└───────────────┘

Selection process:
Start with A1 (ends at 4)
Next pick A4 (starts at 5)
Then A5 (starts at 8)

Result: A1 -> A4 -> A5

Build-Up - 7 Steps

1

Foundation

Understanding Activities and Time Slots

Concept: Activities have start and end times that define when they happen.

Each activity is like a task with a start time and an end time. For example, Activity A might start at 1 PM and end at 4 PM. We represent activities as pairs: (start, end). Understanding these pairs is the first step to solving the problem.

Result

You can list activities as pairs like (1,4), (3,5), (0,6), etc.

Knowing how to represent activities with start and end times is essential because it sets the stage for comparing and selecting them.

2

Foundation

Sorting Activities by Finish Time

Concept: Sorting activities by their end times helps us pick the earliest finishing activities first.

Given a list of activities, we sort them so the one that finishes earliest comes first. For example, sorting [(1,4), (3,5), (0,6)] by end time gives [(1,4), (3,5), (0,6)]. This order helps us pick activities that free up time sooner.

Result

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

Sorting by finish time is the key step that allows a simple greedy choice to work correctly.

3

Intermediate

Greedy Selection of Non-Overlapping Activities

🤔Before reading on: do you think picking the longest activity first or the earliest finishing activity first leads to more total activities? Commit to your answer.

Concept: Choosing the activity that finishes earliest leaves the most time for others, maximizing total activities.

Start with the first activity in the sorted list (earliest finish). Then, pick the next activity that starts after the last selected activity ends. Repeat until no more activities fit. This greedy method ensures maximum activities.

Result

Selected activities: (1,4), (5,7), (8,9)

Understanding that earliest finishing activities free up time for more activities is the heart of the greedy approach.

4

Intermediate

Implementing Activity Selection in Rust

🤔Before reading on: do you think a loop or recursion is better for selecting activities? Commit to your answer.

Concept: We can implement the greedy selection using a simple loop in Rust to pick activities.

```rust fn activity_selection(start: &[i32], finish: &[i32]) -> Vec { let n = start.len(); let mut selected = Vec::new(); let mut last_finish = -1; for i in 0..n { if start[i] > last_finish { selected.push(i); last_finish = finish[i]; } } selected } fn main() { let start = [1, 3, 0, 5, 8, 5]; let finish = [4, 5, 6, 7, 9, 9]; let selected = activity_selection(&start, &finish); for i in selected { println!("Activity {}: {} - {}", i + 1, start[i], finish[i]); } } ```

Result

Output: Activity 1: 1 - 4 Activity 4: 5 - 7 Activity 5: 8 - 9

Knowing how to translate the greedy logic into code solidifies understanding and prepares for real use.

5

Intermediate

Handling Unsorted Input with Sorting

🤔Before reading on: do you think sorting activities by start time or finish time is better for this problem? Commit to your answer.

Concept: Sorting activities by finish time before selection is necessary if input is unsorted.

If activities are not sorted, we first create a list of (start, finish, index) tuples. Then we sort by finish time. After sorting, we apply the greedy selection. This ensures correctness regardless of input order.

Result

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

Sorting before selection is a crucial preprocessing step that guarantees the greedy method works.

6

Advanced

Extending to Weighted Activity Selection

🤔Before reading on: do you think the greedy method works if activities have different values or weights? Commit to your answer.

Concept: When activities have weights, the greedy method fails; dynamic programming is needed.

If each activity has a weight (value), picking earliest finishing activity may not maximize total weight. Instead, we use dynamic programming to consider all combinations and pick the best weighted sum. This is a more complex problem called Weighted Interval Scheduling.

Result

Greedy fails for weights; DP finds max total weight selection.

Recognizing the limits of greedy methods helps choose the right algorithm for weighted scheduling.

7

Expert

Optimizing with Binary Search in Weighted Scheduling

🤔Before reading on: do you think checking all previous activities for compatibility is efficient? Commit to your answer.

Concept: Using binary search to find the last non-conflicting activity speeds up weighted scheduling.

In weighted scheduling, for each activity, we find the last activity that finishes before it starts. Doing this with linear search is slow. Using binary search on sorted finish times reduces complexity from O(n²) to O(n log n). This optimization is key in large datasets.

Result

Weighted scheduling runs efficiently with binary search optimization.

Understanding algorithmic optimizations like binary search in DP improves performance in real-world applications.

Under the Hood

The greedy algorithm works because selecting the earliest finishing activity leaves the maximum remaining time for other activities. Internally, sorting arranges activities so the algorithm can scan once, picking compatible activities by comparing start and finish times. This linear scan after sorting ensures O(n log n) time due to sorting, with selection in O(n).

Why designed this way?

The problem was designed to model real scheduling conflicts simply. The greedy approach was discovered because it guarantees optimality for unweighted activities, avoiding complex computations. Alternatives like brute force check all subsets but are inefficient. The greedy method balances simplicity and optimality.

┌───────────────┐
│ Activities    │
│ (start, end)  │
└──────┬────────┘
       │ Sort by finish time
       ▼
┌───────────────┐
│ Sorted List   │
└──────┬────────┘
       │ Iterate and select
       ▼
┌───────────────┐
│ Selected      │
│ Activities    │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does picking the longest activity first maximize total activities? Commit yes or no.

Common Belief: Choosing the longest activity first will maximize the number of activities selected.

Reality: Picking the longest activity first often reduces the total number of activities because it blocks more time.

Why it matters: If you pick longest activities first, you may end up with fewer total activities, wasting scheduling opportunities.

Quick: Can the greedy method solve weighted activity selection optimally? Commit yes or no.

Common Belief: The greedy approach works for all activity selection problems, including weighted ones.

Reality: Greedy fails for weighted activities; dynamic programming is required for optimal weighted selection.

Why it matters: Using greedy for weighted problems leads to suboptimal schedules and lost value.

Quick: Does sorting by start time instead of finish time work for this problem? Commit yes or no.

Common Belief: Sorting activities by start time is enough to solve the problem optimally.

Reality: Sorting by start time does not guarantee optimal selection; sorting by finish time is necessary.

Why it matters: Sorting incorrectly leads to wrong activity choices and fewer total activities.

Expert Zone

1

The greedy choice property holds only because activities are sorted by finish time, ensuring no better future choice is missed.

2

In weighted scheduling, the compatibility check between activities is a subtle but critical step that affects correctness and performance.

3

The problem assumes activities are indivisible; splitting activities changes the problem to interval partitioning or fractional scheduling.

When NOT to use

Avoid greedy activity selection when activities have weights or values; use weighted interval scheduling with dynamic programming instead. Also, if activities can overlap partially or be split, other scheduling algorithms like interval partitioning or linear programming are better.

Production Patterns

Used in CPU job scheduling, conference room booking systems, and task management apps to maximize resource use. Often combined with priority queues or segment trees for dynamic or online scheduling.

Connections

Interval Partitioning

Related scheduling problem focusing on minimizing resources rather than maximizing activities.

Understanding activity selection helps grasp interval partitioning, which schedules all activities using minimum rooms instead of selecting a subset.

Dynamic Programming

Builds on activity selection when weights are added, requiring more complex optimization.

Knowing greedy activity selection clarifies why dynamic programming is needed for weighted cases, showing limits of simple greedy methods.

Project Management

Scheduling tasks without overlap is a core challenge in managing projects efficiently.

Activity selection principles apply to real-world project timelines, helping managers allocate time and resources effectively.

Common Pitfalls

#1 Selecting activities without sorting by finish time.

Wrong approach:

let start = [1, 3, 0, 5, 8, 5];
let finish = [4, 5, 6, 7, 9, 9];
// No sorting
for i in 0..start.len() {
if start[i] > last_finish {
selected.push(i);
last_finish = finish[i];
}
}

Correct approach:

let mut activities: Vec<(usize, i32, i32)> = start.iter().cloned().zip(finish.iter().cloned()).enumerate().map(|(i, (s, f))| (i, s, f)).collect();
activities.sort_by_key(|&(_, _, f)| f);
for &(i, s, f) in &activities {
if s > last_finish {
selected.push(i);
last_finish = f;
}
}

Root cause:

Not sorting means activities are checked in input order, missing the earliest finishing ones first.

#2 Using greedy method for weighted activities.

Wrong approach:

let weights = [5, 1, 8, 4, 6, 3];
// Greedy selection ignoring weights
for i in 0..start.len() {
if start[i] > last_finish {
selected.push(i);
last_finish = finish[i];
}
}

Correct approach:

// Use dynamic programming with binary search to find max weight
// Pseudocode:
// 1. Sort activities by finish time
// 2. For each activity, find last non-conflicting activity
// 3. Use DP to compute max weight including or excluding current
// 4. Reconstruct solution from DP table

Root cause:

Greedy ignores weights, so it cannot maximize total value.

#3 Comparing start time with last finish time using >= instead of >.

Wrong approach:

if start[i] >= last_finish {
selected.push(i);
last_finish = finish[i];
}

Correct approach:

if start[i] > last_finish {
selected.push(i);
last_finish = finish[i];
}

Root cause:

Allowing start time equal to last finish time may cause overlapping activities if end times are inclusive.

Key Takeaways

The Activity Selection Problem finds the largest set of non-overlapping activities by always choosing the earliest finishing activity first.

Sorting activities by their finish times is essential to apply the greedy selection correctly and efficiently.

Greedy algorithms work perfectly for unweighted activities but fail when activities have weights or values.

Dynamic programming extends the problem to weighted activities, requiring more complex solutions and optimizations like binary search.

Understanding this problem builds a foundation for many real-world scheduling and resource allocation challenges.

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