Activity Selection

Activity Selection is the textbook greedy problem. You are given activities with start and finish times, and you want to attend the maximum number that do not overlap. The whole trick is choosing the right thing to be greedy about.

The slow way first

You might try every possible subset of activities, check which subsets have no overlaps, and keep the biggest. With n activities there are 2^n subsets, so this is exponential — hopeless beyond a handful of activities.

The question to ask: if I greedily commit to one activity at a time, which one should I grab first? Picking the shortest activity, or the earliest-starting one, both fail on simple examples. The winning rule is subtler.

The idea: take the earliest finisher

Sort the activities by finish time. Then walk through them and greedily take every activity whose start is at or after the finish of the last one you took. Each time you take an activity, update last_finish.

Why earliest finisher? The activity that frees up the soonest leaves the most room for everything after it. Greedily grabbing it is always at least as good as any other choice — that is the exchange argument behind the proof.

Walk through it

Step through the animation. The boxes are activities shown as start-finish, already sorted by finish time. The pointer i scans left to right. last_finish starts at minus infinity. Each activity that starts at or after last_finish turns green (selected) and updates last_finish; each overlapping one is greyed out and skipped. We end with 4 activities.

Pseudocode

sort activities by finish time
count = 0
last_finish = -infinity
for each (start, finish) in activities:
    if start >= last_finish:        # no overlap with our last pick
        count = count + 1
        last_finish = finish        # commit to this activity
return count

The Python solution

def max_activities(activities):
    activities.sort(key=lambda a: a[1])
    count, last_finish = 0, float("-inf")
    for start, finish in activities:
        if start >= last_finish:
            count += 1
            last_finish = finish
    return count

• activities.sort(key=lambda a: a[1]) sorts by finish time (a[1]) — the heart of the greedy choice.
• last_finish tracks the finish of the most recently selected activity; it starts at negative infinity so the first activity is always taken.
• Line 5 is the non-overlap test: start >= last_finish means this activity begins no earlier than the previous one ended.
• When we take an activity we bump count and update last_finish so future activities are compared against the new boundary.

Complexity

The sort costs O(n log n) and the scan is a single O(n) pass, so the total is O(n log n). Beyond the sort we only keep a couple of variables, so extra space is O(1).

When this pattern shows up

Practice