Activity Selection Problem

Q: What is the time complexity of the activity selection problem?

Sorting by finish time costs O(n log n) , and the greedy pass after it is O(n) , so the sort dominates. If the activities already come sorted by finish time, the pass alone solves it in O(n) time and O(1) extra space.

Q: What is the N meetings in one room problem?

It is the same problem told with meetings: one room, N meetings, and a meeting can begin only after the previous one has ended. Sort the meetings by end time and take each one that starts after the last one taken ends. To list the meetings, record each index you take, breaking ties in end time by the smaller index.

EasyGreedy Sorting

+10

Activity i runs from time start[i] to time finish[i]. One person does one activity at a time, and the next activity must start strictly after the previous one finishes: an activity that starts at the exact time another finishes cannot follow it.

Return the largest number of activities one person can do.

Function

maxActivities(start: integer-array, finish: integer-array) → integer

startinteger-array: the start time of each activity
finishinteger-array: the finish time of each activity; finish[i] belongs to start[i]
Returnsinteger: the most activities one person can do, one after another

Constraints

1 ≤ start.length == finish.length ≤ 5000
0 ≤ start[i] ≤ finish[i] ≤ 10⁵
An activity may start and finish at the same time. The arrays are not sorted.

Examples

Input: start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
Output: 4
Explanation: Doing 10 to 13, 14 to 19, 21 to 22 and 25 to 30 gives 4. Five is impossible: 10 to 13 clashes with 12 to 16, and 21 to 22 with 20 to 24.

Input: start = [1, 5, 9]finish = [5, 9, 12]
Output: 2
Explanation: The activity from 5 to 9 starts at the exact time the first one finishes, so it cannot follow it. Doing 1 to 5 and then 9 to 12 works, so the answer is 2.

Input: start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
Output: 3
Explanation: The activity from 0 to 100 overlaps all the others. Leaving it out, 2 to 4, 5 to 7 and 8 to 10 fit one after another: 3.

Follow-up

Two people now work in parallel, each doing one activity at a time. How many activities can they do together, and which person should take each one?

Solution

Trying every subset of activities takes exponential time. One greedy rule settles the question instead: among the activities that still fit, always do the one that finishes first. Sorting by finish time turns that rule into a single pass.

Pick the earliest finish, again and again

Correct, but does not finish on the largest tests

Intuition

The activity that finishes earliest of all is at least as good a first pick as any other. It frees you no later, so anything that could follow another first pick can follow it too, and swapping it in keeps the count. After that pick the problem repeats on the activities that start after it finishes.

In the first example you pick 10 to 13, then 14 to 19, then 21 to 22, then 25 to 30: four.

Each pick scans all n activities, so the cost is n times the answer. When all 5000 activities fit one after another, that is 25 million checks.

Algorithm

Set count = 0 and lastFinish = -1, below every start.
Scan all activities for the one with start[i] > lastFinish that finishes first.
If there is none, return count.
Otherwise add 1 to count, set lastFinish to that activity's finish, and scan again.

def maxActivities(start, finish):
    n = len(start)
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    while True:
        # among the activities that start after last_finish, find the one that ends first
        pick = -1
        for i in range(n):
            if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
                pick = i
        if pick == -1:
            return count
        count += 1
        last_finish = finish[pick]

Sort by finish time and take greedily

Intuition

Sort by finish time once and you meet the activities in the order the scans above searched for them. Walk the sorted list holding lastFinish, the finish of the last activity you took. An activity with start[i] > lastFinish is the earliest finishing one that still fits, so take it. Any other clashes with your last pick, so skipping it costs nothing.

Sorted, the first example reads 10 to 13, 12 to 16, 14 to 19, 21 to 22, 20 to 24, 25 to 30. You take the first, third, fourth and sixth: 12 is not after 13, and 20 is not after 22.

Ties in finish time need no rule. Once you take an activity that finishes at t, every other one finishing at t starts at or before t and is skipped.

Algorithm

Sort the activities by finish, moving each start along with its finish.
Set count = 0 and lastFinish = -1.
For each activity in that order, if start[i] > lastFinish, add 1 to count and set lastFinish = finish[i].
Return count.

def maxActivities(start, finish):
    order = sorted(range(len(start)), key=lambda i: finish[i])  # earliest finish first
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    for i in order:
        if start[i] > last_finish:
            count += 1
            last_finish = finish[i]
    return count

Pitfalls and edge cases

Sorting by start time. In the third example, 0 to 100 starts first and blocks the other three.
Picking the shortest activity first. With 1 to 5, 5 to 6 and 6 to 10, the shortest is 5 to 6, which clashes with both others; 1 to 5 and 6 to 10 give 2.
Comparing with ≥ instead of >. In the second example that returns 3 instead of 2.
Sorting finish on its own. Each start has to move with its own finish, or starts pair with the wrong activities.
Starting lastFinish at 0. A lone activity from 0 to 1 is then skipped, because 0 > 0 is false.

Frequently asked questions3

What is the time complexity of the activity selection problem?

Sorting by finish time costs O(n log n), and the greedy pass after it is O(n), so the sort dominates. If the activities already come sorted by finish time, the pass alone solves it in O(n) time and O(1) extra space.

What is the N meetings in one room problem?

It is the same problem told with meetings: one room, N meetings, and a meeting can begin only after the previous one has ended. Sort the meetings by end time and take each one that starts after the last one taken ends. To list the meetings, record each index you take, breaking ties in end time by the smaller index.

Is the activity selection problem dynamic programming?

It can be, but it does not need to be. A table over the activities sorted by finish time, holding the most activities ending with each one, gives the answer in O(n²). The greedy choice is always safe, so one pass is enough. The table becomes the right tool when activities carry values and you maximize their total.

def maxActivities(start, finish):
    # Write code here

Test #1

Test #2

Test #3

Arguments

start = [10, 12, 20, 14, 25, 21]
finish = [13, 16, 24, 19, 30, 22]

Expected Output