Activity Selection Problem in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Activity Selection Problem?

To select the maximum number of activities that don't overlap in time from a given set of activities, each with a start and finish time.

beginner

Which algorithmic approach is commonly used to solve the Activity Selection Problem efficiently?

The greedy algorithm approach, which selects activities based on earliest finish time first.

intermediate

Why do we sort activities by their finish times in the Activity Selection Problem?

Sorting by finish times helps to always pick the activity that leaves the most room for the remaining activities, maximizing the total number selected.

intermediate

What is the time complexity of the greedy solution to the Activity Selection Problem after sorting?

O(n log n) due to sorting the activities by finish time, where n is the number of activities. The selection process itself is O(n).

advanced

Explain the greedy choice property in the context of the Activity Selection Problem.

The greedy choice property means that choosing the activity that finishes earliest is always part of an optimal solution, allowing us to build the solution step-by-step.

What is the first step in solving the Activity Selection Problem using a greedy algorithm?

A Sort activities by their finish times

B Sort activities by their start times

C Select the longest activity first

D Select activities randomly

Sorting activities by their finish times allows the greedy algorithm to pick the earliest finishing activity first.

After selecting an activity, what is the next step in the greedy approach?

A Select the activity with the earliest start time

B Select the next activity that starts before the current one finishes

C Select the next activity that starts after the current one finishes

D Select the activity with the longest duration

We pick the next activity that starts after the current selected activity finishes to avoid overlap.

What does the Activity Selection Problem demonstrate about greedy algorithms?

A Greedy algorithms always find the optimal solution for all problems

B Greedy algorithms require backtracking

C Greedy algorithms are slower than dynamic programming

D Greedy algorithms can find optimal solutions when the problem has the greedy choice property

The problem shows greedy algorithms work well when the problem has the greedy choice property and optimal substructure.

If two activities overlap, what does the greedy algorithm do?

A Select both activities

B Select the one with the earlier finish time

C Select the one with the later start time

D Skip both activities

The algorithm selects the activity that finishes earlier to maximize the number of activities selected.

What is the output of the Activity Selection Problem?

A The maximum number of non-overlapping activities selected

B The earliest start time among activities

C The total duration of all activities

D The list of all activities sorted by start time

The output is the maximum number of activities that can be scheduled without overlapping.

Describe the steps to solve the Activity Selection Problem using a greedy algorithm.

Think about how to pick activities step-by-step without overlap.

Explain why sorting by finish time is important in the Activity Selection Problem.

Consider how finish times affect the ability to schedule more 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