Activity selection
Pick the most activities that do not overlap: always the one that finishes first, if it does not clash with the last one chosen.
We have activities (say, classes in one hall) with a start time s and a finish time f, and want the most of
them without overlaps.
- Time:
O(n log n) - Space:
O(n) - CLRS, section 15.1
Eleven activities; four are chosen: [1, 4), [5, 7), [8, 11) and [12, 16).
def activity_selection(activities):# Each activity is [start, finish); take them in order of finishing time.acts = sorted(activities, key=lambda a: a[1])chosen = []free_from = 0for start, finish in acts:if start >= free_from:chosen.append([start, finish])free_from = finishreturn len(chosen)
Start
acts
The table is still empty.
chosen
The table is still empty.
Local variables
Orange = changed in this step
activities list
Call stack
- activity_selection()line 1
Explanation
The idea
We have activities (say, classes in one hall) with a start time s and a finish time f, and want the most of
them without overlaps.
The greedy choice: sort the activities by finishing time and take each one that starts after the last chosen activity ends.
Why it works
The activity that finishes first leaves the most time for the rest. If an optimal answer does not start with it, its first activity can be swapped for this one without any clash; so the greedy choice is always part of some optimal answer.
Choosing by the earliest start or the shortest length does not always work (see "the longest one first").
What to watch in the trace
- The
actstable holds the sorted activities andchosenthe picks;free_fromis when the hall is free again.