Activity Selection Problem in DSA Python - Build from Scratch

Activity Selection Problem

📖 Scenario: You are organizing a conference with many talks. Each talk has a start time and an end time. You want to attend as many talks as possible without any overlaps.

🎯 Goal: Build a program that selects the maximum number of talks you can attend without overlapping times.

📋 What You'll Learn

Create a list of talks with their start and end times

Sort the talks by their end times

Select talks using the greedy method to avoid overlaps

Print the selected talks in order

💡 Why This Matters

🌍 Real World

Scheduling meetings, classes, or events to maximize attendance without conflicts.

💼 Career

Useful for roles in operations, event planning, project management, and software development involving scheduling algorithms.

1

Create the list of talks

Create a list called talks with these exact tuples representing start and end times: (1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)

DSA Python

# Create the list of talks with start and end times
# Your code here

Hint

Use a list of tuples where each tuple has two numbers: start time and end time.

2

Sort talks by their end times

Create a new list called sorted_talks by sorting talks based on the second element (end time) of each tuple using sorted() with a key=lambda x: x[1].

DSA Python

talks = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
# Sort talks by end time and store in sorted_talks
# Your code here

Hint

Use the sorted() function with a key that picks the end time from each talk tuple.

3

Select the maximum talks without overlap

Create a list called selected_talks starting with the first talk from sorted_talks. Then use a for loop with variable talk to go through sorted_talks[1:]. Inside the loop, if the start time of talk is greater than or equal to the end time of the last selected talk, append talk to selected_talks.

DSA Python

talks = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
sorted_talks = sorted(talks, key=lambda x: x[1])
# Select talks without overlap using a for loop
# Your code here

Hint

Start with the first talk. For each next talk, check if its start time is after or at the end time of the last selected talk.

4

Print the selected talks

Use print(selected_talks) to display the list of talks you can attend without overlap.

DSA Python

talks = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
sorted_talks = sorted(talks, key=lambda x: x[1])
selected_talks = [sorted_talks[0]]
for talk in sorted_talks[1:]:
    if talk[0] >= selected_talks[-1][1]:
        selected_talks.append(talk)
# Print the selected talks
# Your code here

Hint

Use print() to show the final list of talks you can attend.

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