Why Activity Selection Problem in DSA Python?

The Big Idea

What if you could instantly find the best schedule without trying every possibility?

The Scenario

Imagine you have a list of meetings to attend in one room, each with a start and end time. You want to attend as many as possible without overlapping. Doing this by guessing or checking each meeting one by one is confusing and tiring.

The Problem

Manually checking every possible combination of meetings to find the best schedule takes a lot of time and can easily lead to mistakes. You might miss a better option or waste time trying all possibilities.

The Solution

The Activity Selection Problem uses a smart way to pick meetings by always choosing the one that finishes earliest. This simple rule helps you quickly find the maximum number of meetings you can attend without conflicts.

Before vs After

✗ Before

activities = [(1,4), (3,5), (0,6), (5,7)]
# Manually check all combinations to find max meetings

✓ After

activities = sorted(activities, key=lambda x: x[1])
selected = [activities[0]]
for act in activities[1:]:
    if act[0] >= selected[-1][1]:
        selected.append(act)

What It Enables

This concept lets you quickly and correctly schedule the most activities without wasting time or missing better options.

Real Life Example

Scheduling conference talks in a single room so attendees can join the maximum number of talks without overlaps.

Key Takeaways

Manual checking of all meeting combinations is slow and error-prone.

Choosing activities by earliest finish time solves the problem efficiently.

This approach helps maximize the number of non-overlapping 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