Activity Selection: The Classic Greedy Interval Problem

The activity selection problem asks: given a set of activities, each with a start and finish time, what is the largest number you can do if you can only do one at a time? It is the cleanest example of a greedy algorithm that is provably optimal — and the answer is delightfully simple: always pick the activity that finishes earliest among those that still fit.

This is also called interval scheduling maximization, and it shows up everywhere: booking meeting rooms, scheduling jobs on a machine, choosing non-conflicting events.

The problem

You are given n activities. Activity i occupies the half-open interval [start[i], finish[i]). Two activities are compatible if they do not overlap. Select the maximum number of mutually compatible activities.

For example, with intervals (1,3), (2,5), (4,7), (6,8), (5,9), one optimal selection is (1,3), (4,7), (6,8) — three activities.

The greedy rule: earliest finish time

Sort the activities by finish time, then sweep left to right. Keep an activity if its start is at or after the finish of the last one you kept. That is the whole algorithm.

Why finish time and not, say, the shortest activity or the earliest start? Because the activity that ends first leaves the most remaining room for everything after it — and it never costs you a slot (we prove this below).

#include <vector>
#include <algorithm>

// Each activity is {start, finish}. Returns the max count of compatible ones.
int maxActivities(std::vector<std::pair<int,int>> acts) {
    std::sort(acts.begin(), acts.end(),
              [](auto& a, auto& b){ return a.second < b.second; }); // by finish
    int count = 0, lastFinish = INT_MIN;
    for (auto& a : acts) {
        if (a.first >= lastFinish) { // compatible with the last chosen
            count++;
            lastFinish = a.second;
        }
    }
    return count;
}

import java.util.Arrays;

// Each activity is {start, finish}. Returns the max count of compatible ones.
int maxActivities(int[][] acts) {
    Arrays.sort(acts, (a, b) -> Integer.compare(a[1], b[1])); // by finish
    int count = 0, lastFinish = Integer.MIN_VALUE;
    for (int[] a : acts) {
        if (a[0] >= lastFinish) { // compatible with the last chosen
            count++;
            lastFinish = a[1];
        }
    }
    return count;
}

// Each activity is [start, finish]. Returns the max count of compatible ones.
function maxActivities(acts) {
  acts.sort((a, b) => a[1] - b[1]); // by finish
  let count = 0, lastFinish = -Infinity;
  for (const [start, finish] of acts) {
    if (start >= lastFinish) { // compatible with the last chosen
      count++;
      lastFinish = finish;
    }
  }
  return count;
}

# Each activity is (start, finish). Returns the max count of compatible ones.
def max_activities(acts):
    acts.sort(key=lambda a: a[1])  # by finish
    count, last_finish = 0, float("-inf")
    for start, finish in acts:
        if start >= last_finish:   # compatible with the last chosen
            count += 1
            last_finish = finish
    return count

For beginners: “Half-open interval [s, f)” means an activity occupies the time from s up to but not including f. So an activity finishing at 5 is compatible with one starting at exactly 5 — they just touch, they don’t overlap. That is why the check is start >= lastFinish, not start > lastFinish.

Returning the actual activities

Often you want the chosen activities, not just the count. Keep the same loop and collect them:

std::vector<std::pair<int,int>> selectActivities(std::vector<std::pair<int,int>> acts) {
    std::sort(acts.begin(), acts.end(),
              [](auto& a, auto& b){ return a.second < b.second; });
    std::vector<std::pair<int,int>> chosen;
    int lastFinish = INT_MIN;
    for (auto& a : acts)
        if (a.first >= lastFinish) { chosen.push_back(a); lastFinish = a.second; }
    return chosen;
}

import java.util.*;

List<int[]> selectActivities(int[][] acts) {
    Arrays.sort(acts, (a, b) -> Integer.compare(a[1], b[1]));
    List<int[]> chosen = new ArrayList<>();
    int lastFinish = Integer.MIN_VALUE;
    for (int[] a : acts)
        if (a[0] >= lastFinish) { chosen.add(a); lastFinish = a[1]; }
    return chosen;
}

function selectActivities(acts) {
  acts.sort((a, b) => a[1] - b[1]);
  const chosen = [];
  let lastFinish = -Infinity;
  for (const a of acts)
    if (a[0] >= lastFinish) { chosen.push(a); lastFinish = a[1]; }
  return chosen;
}

def select_activities(acts):
    acts.sort(key=lambda a: a[1])
    chosen, last_finish = [], float("-inf")
    for a in acts:
        if a[0] >= last_finish:
            chosen.append(a)
            last_finish = a[1]
    return chosen

Why earliest-finish is optimal

This is a textbook exchange argument (see when greedy works). Let g be the activity that finishes earliest overall. Take any optimal solution O, and let a be its earliest-finishing activity. Since g finishes no later than a, swapping a for g in O keeps it valid (nothing else started before a finished, so nothing started before g finished either) and keeps the count the same. So there is an optimal solution containing the greedy choice g. Remove g and everything overlapping it, and the same argument applies to the smaller problem — by induction, greedy is optimal.

Complexity

• Time: O(n log n), dominated by the sort. The sweep itself is O(n).
• Space: O(1) extra for the count version (O(n) if you collect the chosen activities or count the sort’s overhead).

Going deeper: A related problem — finding the minimum number of rooms to host all activities — is not solved by this rule. That one sorts start and finish times separately and tracks concurrent overlaps (a sweep-line / heap approach). Same intervals, different objective, different greedy.

Pitfall: Sorting by start time, by duration, or by fewest conflicts all seem reasonable and all fail on some input. Only earliest finish time is provably optimal. Practice spotting why on the greedy exercises.

Next: greedy applied to compression — Huffman coding.