Activity Selection Problem in DSA Python - Execution Trace

Concept Flow - Activity Selection Problem

Sort activities by finish time

↓

Select first activity

↓

For each next activity

↓

Check if start >= last selected finish

↓

Select activity

↓

Repeat until all activities checked

↓

Return selected activities

Sort activities by finish time, then pick the earliest finishing compatible activities one by one.

Execution Sample

DSA Python

activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
for i in activities[1:]:
    if i[0] >= selected[-1][1]:
        selected.append(i)
print(selected)

Select maximum number of non-overlapping activities sorted by finish time.

Execution Table

Step	Operation	Current Activity	Last Selected Activity	Condition (start >= last finish)	Action	Selected Activities
1	Sort activities by finish time	-	-	-	-	[(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)] sorted to [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
2	Select first activity	(1,4)	-	-	Select	[(1,4)]
3	Check next activity	(3,5)	(1,4)	3 >= 4? False	Skip	[(1,4)]
4	Check next activity	(0,6)	(1,4)	0 >= 4? False	Skip	[(1,4)]
5	Check next activity	(5,7)	(1,4)	5 >= 4? True	Select	[(1,4),(5,7)]
6	Check next activity	(3,9)	(5,7)	3 >= 7? False	Skip	[(1,4),(5,7)]
7	Check next activity	(5,9)	(5,7)	5 >= 7? False	Skip	[(1,4),(5,7)]
8	Check next activity	(6,10)	(5,7)	6 >= 7? False	Skip	[(1,4),(5,7)]
9	Check next activity	(8,11)	(5,7)	8 >= 7? True	Select	[(1,4),(5,7),(8,11)]
10	Check next activity	(8,12)	(8,11)	8 >= 11? False	Skip	[(1,4),(5,7),(8,11)]
11	Check next activity	(2,14)	(8,11)	2 >= 11? False	Skip	[(1,4),(5,7),(8,11)]
12	Check next activity	(12,16)	(8,11)	12 >= 11? True	Select	[(1,4),(5,7),(8,11),(12,16)]
13	End of activities	-	-	-	-	Final selected activities: [(1,4),(5,7),(8,11),(12,16)]

💡 All activities checked, selection complete.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 12	Final
selected	[]	[(1,4)]	[(1,4),(5,7)]	[(1,4),(5,7),(8,11)]	[(1,4),(5,7),(8,11),(12,16)]	[(1,4),(5,7),(8,11),(12,16)]
current_activity	-	(3,5)	(3,9)	(8,12)	-	-
last_selected_activity	-	(1,4)	(5,7)	(8,11)	(12,16)	(12,16)

Key Moments - 3 Insights

Why do we sort activities by their finish time first?

Sorting by finish time ensures we always pick the activity that frees the schedule earliest, allowing more activities to fit later. See Step 1 in execution_table.

Why do we compare current activity's start time with last selected activity's finish time?

To avoid overlap, we only select activities starting after or exactly when the last selected one finishes. This is shown in the Condition column in execution_table steps 3-12.

Why do we skip activities that start before the last selected activity finishes?

Because they overlap and can't be done together. Skipping them keeps the schedule conflict-free, as seen in the 'Skip' action rows in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5. What is the selected activities list after this step?

A [(5,7)]

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

C [(1,4)]

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

💡 Hint

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

At which step does the condition 'start >= last finish' become false for activity (3,5)?

A Step 4

B Step 6

C Step 3

D Step 7

💡 Hint

Look at the 'Condition' column for activity (3,5) in execution_table.

If the activity (8,12) had a finish time of 10 instead, how would the selection change at Step 10?

A It would be selected instead of (8,11)

B It would still be skipped

C It would be selected along with (8,11)

D It would replace (5,7)

💡 Hint

Compare finish times and selection logic in execution_table Steps 9 and 10.

Concept Snapshot

Activity Selection Problem:
- Sort activities by finish time
- Select first activity
- For each next activity, select if start >= last selected finish
- Skip otherwise
- Result: max number of non-overlapping activities

Full Transcript

The Activity Selection Problem finds the maximum number of activities that don't overlap. We first sort activities by their finish times. Then we pick the first activity. For each next activity, we check if its start time is at or after the finish time of the last selected activity. If yes, we select it; if no, we skip it. This process continues until all activities are checked. The final list contains the maximum compatible activities.

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