Activity Selection

Greedy O(n log n) O(1)

Picks the maximum number of non-overlapping activities by always taking the one that finishes earliest.

01234567891011

1–2

3–4

0–6

5–7

8–9

5–9

6–10

8–11

Sorted by finish time — the line marks the last finish.

1/20

Activities are sorted by finish time — earliest finisher first.

InvariantTaking the earliest finisher leaves the most room for the rest — so a greedy choice is never worse than an optimal one.

consideringselectedrejected

activity-selection.c

/* activities sorted by finish time */
void activitySelect(int start[], int finish[], int n) {
    int lastFinish = finish[0];
    printf("select 0\n");
    for (int i = 1; i < n; i++) {
        if (start[i] >= lastFinish) {
            printf("select %d\n", i);
            lastFinish = finish[i];
        }
    }
}

How Activity Selection works

Sort by finish time and always take the activity that frees you earliest. Anything that finishes earliest can be swapped into some optimal solution, so the greedy choice is always safe.

When to use it

Interval scheduling on one resource: meeting rooms, machines, CPU time slots.