Activity Selection Problem in DSA Python - Time & Space Complexity

Time Complexity: Activity Selection Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to pick activities grows as the number of activities increases.

How does the program's work change when we have more activities to choose from?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code selects the maximum number of activities that don't overlap, assuming activities are sorted by finish time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that checks each activity once.
• How many times: The loop runs (n - 1) times, where n is the number of activities.

How Execution Grows With Input

As the number of activities grows, the program checks each one once to decide if it fits.

Input Size (n)	Approx. Operations
10	About 9 checks
100	About 99 checks
1000	About 999 checks

Pattern observation: The number of operations grows directly with the number of activities.

Final Time Complexity

Time Complexity: O(n)

This means the time to select activities grows in a straight line with the number of activities.

Common Mistake

[X] Wrong: "The algorithm checks every pair of activities, so it must be O(n²)."

[OK] Correct: The code only checks each activity once in order, not every pair, so it runs much faster.

Interview Connect

Understanding this linear time solution shows you can spot efficient ways to handle scheduling problems, a useful skill in many real tasks.

Self-Check

"What if the activities were not sorted by finish time? How would the time complexity change?"

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