Activity Selection Problem in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Activity Selection

What is the output of the following code that selects the maximum number of non-overlapping activities?

DSA Python

def activity_selection(start, finish):
    n = len(start)
    selected = [0]
    last_finish = finish[0]
    for i in range(1, n):
        if start[i] >= last_finish:
            selected.append(i)
            last_finish = finish[i]
    return selected

start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
print(activity_selection(start, finish))

A [1, 3, 4]

B [0, 2, 3, 5]

C [0, 1, 4]

D [0, 1, 3, 4]

💡 Hint

Look for activities that start after or exactly when the last selected activity finishes.

The code selects activities greedily by earliest finish time. It starts with activity 0, then picks activity 1 (start 3 >= finish 2), then activity 3 (start 5 >= finish 4), then activity 4 (start 8 >= finish 7).

🧠 Conceptual

intermediate

Key Idea Behind Activity Selection

What is the main idea behind the greedy approach to solve the Activity Selection Problem?

A Always pick the activity that finishes earliest among the remaining activities.

B Always pick the activity with the earliest start time.

C Always pick the activity with the shortest duration.

D Always pick the activity that starts latest.

💡 Hint

Think about which choice leaves the most room for other activities.

Choosing the activity that finishes earliest allows more time for the remaining activities, maximizing the total number selected.

🔧 Debug

advanced

Identify the Bug in Activity Selection Code

What error does the following code produce when run, and why? ```python def activity_selection(start, finish): n = len(start) selected = [] last_finish = 0 for i in range(n): if start[i] >= last_finish: selected.append(i) last_finish = finish[i] return selected start = [1, 3, 0, 5, 8, 5] finish = [2, 4, 6, 7, 9, 9] print(activity_selection(start, finish)) ```

A The code outputs [2, 3, 4] which is incorrect because activities are not sorted by finish time.

B The code outputs [0, 1, 3, 4] correctly.

C The code raises an IndexError due to wrong indexing.

D The code outputs an empty list because last_finish is initialized to 0.

💡 Hint

Check if the activities are sorted by finish time before selection.

The code does not sort activities by finish time, so it picks activities in input order, leading to a suboptimal and incorrect selection.

🚀 Application

advanced

Maximum Activities Count

Given the start and finish times below, what is the maximum number of activities that can be selected without overlap? start = [4, 1, 3, 0, 5, 8, 5] finish = [5, 2, 4, 6, 7, 9, 9]

A 3

B 6

C 5

D 4

💡 Hint

Sort activities by finish time and count how many can fit without overlapping.

After sorting by finish times: activities with finish times 2,4,5,6,7,9,9. Selecting activities 1,2,0,4,5 gives 5 activities without overlap.

🧠 Conceptual

expert

Why Greedy Works for Activity Selection

Why does the greedy algorithm that selects the earliest finishing activity always produce an optimal solution for the Activity Selection Problem?

A Because activities with earliest start times always lead to optimal solutions.

B Because selecting the earliest finishing activity leaves the maximum remaining time for other activities, ensuring maximum count.

C Because the problem requires selecting the longest activities first.

D Because the algorithm tries all possible combinations and picks the best.

💡 Hint

Think about how the choice affects the remaining activities.

Choosing the earliest finishing activity frees up the timeline for more activities to fit, which is why the greedy approach is optimal.

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