DSA Activity Selection and the Exchange Argument

The problem

Activity selection picks the largest set of activities that do not overlap in time. Each activity is a pair holding a start and a finish. Activities that touch at one endpoint, like one ending at 4 and one starting at 4, do not overlap.

The answer in this article is the chosen list of activities. Its size is the largest size any valid schedule can reach. No two chosen activities may overlap.

first = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
second = [(9, 10), (9, 11), (10, 12), (11, 12), (12, 13)]
print('first case activities:', len(first))
print('second case activities:', len(second))

The first case holds eleven activities and admits a schedule of four. The second case holds five and admits a schedule of three. Both answers appear in the optimal section.

Intuition: take the earliest start, or the shortest activity

The first idea takes the activity that starts earliest. Another early idea takes the shortest activity. Both sound plausible, and both can block the room for longer than the best choice would.

The trap is a long early activity. It starts first and runs long, and it blocks two shorter activities that would both have fit after a quicker finish. The next block shows that loss in numbers.

activities = [(0, 10), (1, 3), (4, 6), (7, 9)]
earliest_start = min(activities)
print('earliest start activity:', earliest_start)
blocked = [a for a in activities if a != earliest_start and a[0] < earliest_start[1]]
print('activities it blocks:', blocked)
print('schedule size with earliest start: 1')
print('schedule size without it: 3')

Taking the long activity gives a schedule of one. Skipping it gives a schedule of three. The rule that survives is about finish times, not start times or lengths alone.

Brute force: test every subset

The brute force tests every subset of the activities. A subset is valid when no two of its activities overlap. The largest valid subset is the answer.

A counter records the subsets tested. The count doubles with each added activity. That growth is the cost the greedy rule removes.

import itertools
def brute(activities):
    tested = [0]
    best = []
    n = len(activities)
    for size in range(n, -1, -1):
        for combo in itertools.combinations(activities, size):
            tested[0] += 1
            ordered = sorted(combo)
            ok = True
            for i in range(1, len(ordered)):
                if ordered[i][0] < ordered[i - 1][1]:
                    ok = False
            if ok:
                return list(combo), tested[0]
    return best, tested[0]
acts = [(0, 10), (1, 3), (4, 6), (7, 9)]
best, tested = brute(acts)
print('best schedule:', best)
print('subsets tested:', tested)

The brute force confirms the schedule of three for the trap case. It tested subsets in falling size order and stopped at the first valid one. A full count without that early stop would test every subset.

The optimal solution: always take the earliest finish

The greedy rule keeps taking the activity that finishes earliest among those still free, and an activity fits when it starts at or after the last chosen finish. That one sentence is the whole method.

The exchange argument proves the rule. Swapping the earliest finish in for the first activity of any best schedule keeps that schedule valid and the same size. Repeating the swap turns any best schedule into the greedy schedule, so the greedy schedule is as large as any schedule can be.

def select(activities):
    chosen = []
    last_finish = -1
    checks = [0]
    for start, finish in sorted(activities, key=lambda item: item[1]):
        checks[0] += 1
        if start >= last_finish:
            chosen.append((start, finish))
            last_finish = finish
    return chosen, checks[0]
first = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
second = [(9, 10), (9, 11), (10, 12), (11, 12), (12, 13)]
for activities in (first, second):
    chosen, checks = select(activities)
    print('activities:', len(activities), 'checks:', checks)
    print('chosen:', chosen)
    print('count:', len(chosen))

Both cases from the start of the article are answered in one sorted walk each. The first case takes four activities. The second takes three, and two of its activities touch at endpoints without overlapping.

Walkthrough: the greedy walk on a small set

The walk visits activities in finish order. The state is the last chosen finish. Each step either takes the activity or skips it with the reason printed.

activities = [(1, 4), (3, 5), (5, 7), (8, 11)]
chosen = []
last_finish = -1
for start, finish in sorted(activities, key=lambda item: item[1]):
    if start >= last_finish:
        chosen.append((start, finish))
        last_finish = finish
        print('take', (start, finish))
    else:
        print('skip', (start, finish), 'starts before', last_finish)
print('chosen:', chosen)

The activity from 3 to 5 is skipped because it starts before 4. Every other activity is taken. The final list is read straight off the walk, with no subset ever built.

Complexity

Sorting by finish time costs O(n log n) for n activities. The walk after the sort is one pass, so its time is O(n) and its extra space is O(1) beyond the chosen list.

for n in [4, 11, 20]:
    print('activities', n, '- greedy checks:', n, ' brute subsets:', 2 ** n)

At 20 activities the greedy walk makes 20 checks. The brute force would test over a million subsets. The sort is the only non-linear step, and it is paid once.

Edge cases and pitfalls

Sorting by start time instead of finish time is the classic mistake. The trap case in the intuition section is exactly that mistake, and it costs two activities there. The sort key is the finish, always.

An empty list gives an empty schedule. Activities that merely touch do not overlap, so a start equal to the last finish is always taken. A strict greater-than test in that spot would wrongly skip every touching activity.

def select(activities):
    chosen = []
    last_finish = -1
    for start, finish in sorted(activities, key=lambda item: item[1]):
        if start >= last_finish:
            chosen.append((start, finish))
            last_finish = finish
    return chosen
print('empty:', select([]))
print('single:', select([(2, 5)]))
print('touching:', select([(1, 4), (4, 6)]))
print('all overlapping:', select([(0, 10), (1, 9), (2, 8)]))

The touching pair is fully taken. The all-overlapping set keeps only its earliest finish. Both answers follow from the single fit rule, start at or after the last finish.