Activity Selection Algorithm

You have a conference room. Ten meetings want to use it. Some overlap. How do you fit the most meetings into a single day?

That's the Activity Selection Problem. It shows up everywhere — scheduling jobs on a server, booking resources, organizing events.

The Intuition

The greedy insight is simple: always pick the activity that finishes earliest. The sooner something ends, the more room you leave for whatever comes next.

Sort by finish time. Pick the first one. Skip anything that conflicts. Repeat.

That's it. No dynamic programming. No recursion. Just greed — and it works.

The Code

function activitySelection(startTimes, finishTimes) {
  const n = startTimes.length;
  const selected = [0];
  let lastFinish = finishTimes[0];

  for (let i = 1; i < n; i++) {
    if (startTimes[i] >= lastFinish) {
      selected.push(i);
      lastFinish = finishTimes[i];
    }
  }

  return selected;
}

const start  = [1, 3, 0, 5, 8, 5];
const finish = [2, 4, 6, 7, 9, 9];
console.log(activitySelection(start, finish));
// [0, 1, 3, 4] → activities at indices 0, 1, 3, 4

This assumes the activities are already sorted by finish time. If they aren't, sort them first.

Complexity

• Time: O(n log n) if you need to sort, O(n) if already sorted.
• Space: O(n) for the selected list.

Why Greedy Works Here

Greedy algorithms don't always give optimal results. But for activity selection, you can prove it: picking the earliest-finishing activity never blocks a better solution. Any other choice either picks the same number of activities or fewer.

The Trade-off

This approach maximizes the count of activities. It doesn't care about duration or priority. If you need to maximize total time used or assign weights to activities, you need a different approach — weighted interval scheduling with dynamic programming.