Skip to main content

Activity Selection

Given activities as half-open intervals [si,fi)[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

Exchange proof​

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

Cost and boundary​

  • Sorting: O(nlog⁡n)O(n\log n); selection scan: O(n)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.

Source​