Chapter 45

Home

Activity Selection Problem

Given N activities with start and end times, pick the maximum number that don't overlap. This is the quintessential greedy algorithm — and the proof of why sorting by end time (not start time) gives the optimal answer.

The Problem

You have a single room. Activities have a start time sᵢ and finish time fᵢ. Choose as many non-overlapping activities as possible. Two activities overlap if one starts before the other finishes — [1, 3) and [3, 5) are compatible (they meet at a point).

0 10 A [1,4] B [3,6] C [5,7] D [8,11] A and B overlap → pick one Optimal: A, C, D = 3 activities

The Greedy Strategy: Sort by Finish Time

Sort activities by finish time. Always pick the activity with the earliest finish time that doesn't conflict with the last picked one. This leaves the maximum remaining time for other activities.

C++ — activity selection

struct Activity { int start, finish; };

int select_activities(vector<Activity>& acts) {
    // Sort by finish time (earliest first)
    sort(acts.begin(), acts.end(),
         [](auto& a, auto& b) { return a.finish < b.finish; });

    int count = 0, last_finish = 0;
    for (auto& a : acts) {
        if (a.start >= last_finish) {  // compatible
            count++;
            last_finish = a.finish;
        }
    }
    return count;
}

Rust — activity selection

struct Activity { start: i32, finish: i32 }

fn select_activities(mut acts: Vec<Activity>) -> usize {
    acts.sort_by_key(|a| a.finish);

    let mut count = 0;
    let mut last_finish = 0;
    for a in &acts {
        if a.start >= last_finish {
            count += 1;
            last_finish = a.finish;
        }
    }
    count
}

💡 Why sort by finish, not start?

Sorting by start time would pick the earliest-starting activity first — but it might be a long one that blocks everything else. Sorting by finish time ensures you always free up the room as early as possible, maximising room for future activities. This is the greedy choice property in action.

Proof Sketch (Exchange Argument)

The classic exchange argument for why this greedy works:

1. Any optimal solution can be transformed to include the first greedy choice

Let the earliest-finishing activity be a₁. In any optimal solution, if it doesn't include a₁, replace the first activity in the optimal solution with a₁. It can only make the remaining time more — never less.

2. Repeat for the subproblem

After picking a₁, the problem reduces to "select activities starting at or after a₁'s finish time." The same logic applies recursively. By induction, the greedy choice property holds at every step.

// Key intuition:
// Picking the activity that finishes earliest
// maximises the remaining time for everything else.
// This is always safe — no optimal solution
// can benefit from leaving the room idle.

Key Takeaways

Practice