Activity Selection

Given activities as half-open intervals $[s_i,f_i)$, select the largest number of pairwise non-overlapping activities for one resource. All activities have equal value; the objective is cardinality, not occupied time or profit.

Greedy rule

Sort by nondecreasing finish time, then accept each activity whose start is at least the finish of the last accepted activity.

def select_activities(activities: list[tuple[int, int]]):
    selected = []
    last_finish = float("-inf")
    for start, finish in sorted(activities, key=lambda item: item[1]):
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish
    return selected

Open full-size image

Time runs left to right; rows are ordered from earliest to latest finish. Scan downward: select the first blue interval, then skip candidates that overlap it and select the next compatible interval. The dotted line marks each selected finish time. This larger textbook example illustrates the scan rather than the four-interval trace below. The book requires a strictly later start; this page uses half-open intervals, so touching endpoints are compatible.

Jeff Erickson, Algorithms, Figure 4.2 (p. 163); cropped from the PDF. · CC BY 4.0

Exchange proof

Let $g$ be the earliest-finishing activity and $o$ the first activity of an optimal schedule. Replacing $o$ with $g$ cannot invalidate later activities because $g$ finishes no later. Therefore some optimal solution begins with $g$; the remaining compatible activities form the same problem.

Cost and boundary

• Sorting: $O(n\log n)$; selection scan: $O(n)$.
• If activities arrive already sorted by finish time, the algorithm is linear.
• Weighted interval scheduling is different: earliest finish need not maximize value, and dynamic programming is the standard approach.

State whether touching endpoints are compatible; the comparison changes with the interval convention.

Trace, assumptions, and a weighted counterexample

Require start < finish: zero-duration empty intervals need a separate convention and are outside this implementation's contract. For [(0,3),(1,2),(2,4),(3,5)], sorting by finish gives (1,2),(0,3),(2,4),(3,5). Select (1,2), reject (0,3), select (2,4), reject (3,5): two activities. Each iteration consumes one candidate, so the scan terminates; empty input gives an empty schedule. Python's sorted allocates O(n) auxiliary storage, even excluding the output.

If (0,1) and (1,2) each pay 1, but (0,2) pays 100, earliest finish can choose the two short intervals and earn only 2. Weighted scheduling instead sorts by finish and uses OPT[i] = max(OPT[i-1], value[i] + OPT[p(i)]), where OPT[i] covers the first i activities, p(i) is the index of the last earlier compatible activity (zero if none), and OPT[0]=0. The extra state compares excluding and including an activity rather than assuming a count-optimal choice is profit-optimal.

assert select_activities([(0, 3), (1, 2), (2, 4), (3, 5)]) == [(1, 2), (2, 4)]
assert select_activities([]) == []

Source

• MIT OpenCourseWare: Greedy Scheduling

My reading · Opened notes are remembered in this browser.