Activity Selection Problem in DSA Python

Mental Model

Choose the most activities that don't overlap by always picking the earliest finishing one first.

Analogy: Imagine you have a single meeting room and many meetings to schedule. To fit the most meetings, always pick the one that ends soonest so you can fit more after it.

Activities sorted by finish time:
[Activity1: start=1, end=4] -> [Activity2: start=3, end=5] -> [Activity3: start=0, end=6] -> [Activity4: start=5, end=7] -> [Activity5: start=8, end=9] -> null

Dry Run Walkthrough

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

Goal: Select the maximum number of non-overlapping activities

Step 1: Sort activities by finish time

[1,4] -> [3,5] -> [0,6] -> [5,7] -> [8,9] -> null

Why: Sorting by finish time helps pick activities that free the room earliest

Step 2: Select first activity (1,4)

[1,4] (selected) -> [3,5] -> [0,6] -> [5,7] -> [8,9] -> null

Why: First activity finishes earliest, so pick it

Step 3: Skip (3,5) and (0,6) because they overlap with (1,4)

[1,4] (selected) -> [3,5] (skipped) -> [0,6] (skipped) -> [5,7] -> [8,9] -> null

Why: These activities start before (1,4) ends, so they overlap

Step 4: Select (5,7) since it starts after (1,4) ends

[1,4] (selected) -> [5,7] (selected) -> [8,9] -> null

Why: No overlap with previously selected activities

Step 5: Select (8,9) since it starts after (5,7) ends

[1,4] (selected) -> [5,7] (selected) -> [8,9] (selected) -> null

Why: No overlap with previously selected activities

Result:

[1,4] -> [5,7] -> [8,9] -> null (maximum activities selected: 3)

Annotated Code

DSA Python

from typing import List, Tuple

class ActivitySelector:
    def __init__(self, activities: List[Tuple[int, int]]):
        self.activities = activities

    def select_activities(self) -> List[Tuple[int, int]]:
        # Sort activities by their finish time
        self.activities.sort(key=lambda x: x[1])
        selected = []
        last_finish = -1
        for start, finish in self.activities:
            if start >= last_finish:
                selected.append((start, finish))
                last_finish = finish
        return selected

if __name__ == '__main__':
    activities = [(1,4), (3,5), (0,6), (5,7), (8,9)]
    selector = ActivitySelector(activities)
    result = selector.select_activities()
    for act in result:
        print(f"{act[0]} -> {act[1]}")

self.activities.sort(key=lambda x: x[1])

Sort activities by finish time to prioritize earliest finishing

for start, finish in self.activities:

Iterate over sorted activities to check for selection

if start >= last_finish:

Select activity only if it starts after last selected activity ends

selected.append((start, finish))

Add current activity to selected list

last_finish = finish

Update last_finish to current activity's finish time

Output

1 -> 4

5 -> 7

8 -> 9

Complexity Analysis

Time: O(n log n) because we sort the activities by finish time and then iterate once

Space: O(n) to store the selected activities in the worst case

vs Alternative: Naive approach tries all subsets with exponential time; greedy sorting reduces it to O(n log n)

Edge Cases

Empty list of activities

Returns empty selection without error

DSA Python

for start, finish in self.activities:

All activities overlap completely

Selects only one activity with earliest finish

DSA Python

if start >= last_finish:

Activities with same finish time

Selects the first one encountered, skipping overlapping ones

DSA Python

self.activities.sort(key=lambda x: x[1])

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 by not checking start >= last_finish
Fix: Always check if current activity starts after or exactly when last selected activity finishes

Summary

Selects the maximum number of non-overlapping activities by always picking the earliest finishing one.

Use when you want to schedule as many activities as possible without time conflicts.

The key insight is sorting activities by finish time lets you greedily pick the best next activity.

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 times

D. Calculate the total duration of all activities

Solution

1. Step 1: Understand the problem goal

   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 A

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 of the following is the correct Python syntax to sort a list of activities by their finish times stored as tuples (start, finish)?

easy

A. activities.sort(key=lambda x: x[0])

B. activities.sort(key=lambda x: x[1])

C. activities.sort(reverse=True)

D. activities.sort(key=lambda x: x[0], reverse=True)

Solution

1. Step 1: Identify sorting key for finish times

   Finish time is the second element in the tuple, so index 1 is used as the key.

2. Step 2: Choose correct sort syntax

   Using activities.sort(key=lambda x: x[1]) sorts by finish time ascending, which is required.

3. Final Answer:

   activities.sort(key=lambda x: x[1]) -> Option B

4. Quick Check:

   Sort by finish time = key index 1 [OK]

Hint: Sort by finish time using key=lambda x: x[1] [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Using reverse sort without reason
• Incorrect lambda index for key

3. What is the output of the following code?

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
activities.sort(key=lambda x: x[1])
selected = []
last_finish = 0
for start, finish in activities:
    if start >= last_finish:
        selected.append((start, finish))
        last_finish = finish
print(selected)

medium

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

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

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

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

Solution

1. Step 1: Sort activities by finish time

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

2. Step 2: Select activities greedily

   Start with last_finish=0
   - (1,4): start=1 >=0, select, last_finish=4
   - (3,5): start=3 <4, skip
   - (0,6): start=0 <4, skip
   - (5,7): start=5 >=4, select, last_finish=7
   - (8,9): start=8 >=7, select, last_finish=9
   - (5,9): start=5 <9, 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 first [OK]

Common Mistakes:

• Selecting overlapping activities
• Not updating last_finish correctly
• Sorting incorrectly

4. Find the error in this code snippet for the Activity Selection Problem:

activities = [(1, 4), (4, 5), (2, 6)]
activities.sort(key=lambda x: x[1])
selected = []
last_finish = 0
for start, finish in activities:
    if start > last_finish:
        selected.append((start, finish))
        last_finish = finish
print(selected)

medium

A. Using 'start > last_finish' instead of 'start >= last_finish'

B. Missing parentheses in print statement

C. Not initializing selected list

D. Sorting by start time instead of finish time

Solution

1. Step 1: Check sorting key

   Correctly sorts activities by finish time (second element, index 1).

2. Step 2: Check condition in if statement

   Condition uses 'start > last_finish' which excludes activities starting exactly at last_finish time, missing valid selections. It should be 'start >= last_finish'.

3. Final Answer:

   Using 'start > last_finish' instead of 'start >= last_finish' -> Option A

4. Quick Check:

   Condition must allow equal start time [OK]

Hint: Use >= to allow back-to-back activities [OK]

Common Mistakes:

• Using > excludes valid activities
• Sorting by start time only
• Forgetting to update last_finish

5. Given activities with start and finish times:
[(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]
How many activities can be selected to maximize the count without overlap, and which are they?

hard

A. 2 activities: (0, 6), (8, 9)

B. 3 activities: (0, 6), (5, 7), (8, 9)

C. 5 activities: (1, 2), (3, 4), (5, 7), (8, 9), (5, 9)

D. 4 activities: (1, 2), (3, 4), (5, 7), (8, 9)

Solution

1. Step 1: Sort activities by finish time

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

2. Step 2: Select activities greedily

   Start last_finish=0
   - (1,2): start=1 >=0, select, last_finish=2
   - (3,4): start=3 >=2, select, last_finish=4
   - (0,6): start=0 <4, skip
   - (5,7): start=5 >=4, select, last_finish=7
   - (8,9): start=8 >=7, select, last_finish=9
   - (5,9): start=5 <9, skip
   Total selected = 4 activities

3. Final Answer:

   4 activities: (1, 2), (3, 4), (5, 7), (8, 9) -> Option D

4. Quick Check:

   Max count = 4 selected activities [OK]

Hint: Sort by finish time, pick earliest finishing activities [OK]

Common Mistakes:

• Including overlapping activities
• Counting all activities without checking overlap
• Choosing activities with longer duration instead of earliest finish