Activity Selection (Greedy)

The problem

You are given n activities, each with a start and a finish time. You can attend only one at a time. Choose the largest set of activities that do not overlap.

Greedy rule

1. Sort the activities by finish time.
2. Take the first one.
3. Walk through the rest. Take an activity if its start is at or after the finish of the last one you took. Otherwise skip it.

sort by finish time
last ← −∞;  chosen ← [ ]
for each activity (s, f):
    if s ≥ last:  choose it;  last ← f

Worked example

Sorted by finish: a1 [1,4], a2 [3,5], a3 [0,6], a4 [5,7], a5 [3,9], a6 [5,9], a7 [6,10], a8 [8,11], a9 [8,12], a10 [2,14], a11 [12,16].

Chosen: a1, a4, a8, a11, 4 activities, the maximum possible.

Why the greedy choice is safe

Suppose an optimal solution starts with some other activity. Replace its first activity by the one with the earliest finish. That one ends no later, so everything that followed still fits, and the solution is no worse. Repeating the argument shows greedy is optimal.

Wrong greedy rules

• Earliest start can pick one very long activity that blocks everything (a3 [0,6] or a10 [2,14] above).
• Shortest duration can pick a short event in the middle that overlaps two longer ones that could have both been chosen.

Only the earliest finish rule always works. This is a typical exam question on greedy correctness, together with Huffman coding and Prim/Kruskal.

Code

def select_activities(acts):
    acts = sorted(acts, key=lambda a: a[1])
    chosen, last = [], float('-inf')
    for s, f in acts:
        if s >= last:
            chosen.append((s, f))
            last = f
    return chosen

print(select_activities([(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]))
# [(1, 4), (5, 7), (8, 11), (12, 16)]

Common mistakes

• Sorting by start time or duration instead of finish time.
• Using s > last when the problem allows back-to-back events (s ≥ last).
• Forgetting to update last after choosing an activity.