Activity Selection

The Activity Selection Problem is a classic greedy problem. You have a list of activities, each with a start time and end time. You want to select the maximum number of non-overlapping activities. It is like scheduling meetings in a room — you want to fit as many as possible without double-booking.

Simple enough, right? The tricky part is figuring out which activities to pick. There are tons of possible combinations, and you could spend forever trying every one. Greedy gives you a clean, fast solution.

The Greedy Approach

The key insight is to sort activities by their end time. Why? Because an activity that finishes earlier leaves more room for other activities. You always want the activity that gets out of the way fastest.

After sorting, you pick the first activity (earliest end time), then skip all activities that overlap with it, pick the next non-overlapping one, and repeat. That is it. No backtracking, no second-guessing.

Step by Step Example

function activitySelection(activities) {
  activities.sort((a, b) => a.end - b.end);
  const selected = [activities[0]];
  let lastEnd = activities[0].end;

  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }
  return selected;
}

const acts = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 3, end: 9 },
  { start: 5, end: 9 },
  { start: 6, end: 10 },
  { start: 8, end: 11 },
  { start: 8, end: 12 },
  { start: 2, end: 14 },
];

console.log(activitySelection(acts));

We sort by end time, then walk through. Each time an activity starts after the last one finishes, we select it. The output is the list of chosen activities — the maximum possible set of non-overlapping ones.

Time Complexity

Sorting takes O(n log n). The selection pass is O(n) since we look at each activity once. Total time is O(n log n), dominated by the sort. Space is O(1) extra if you just count activities, or O(n) if you store the selected list.

This is way better than the O(2^n) brute force approach of checking every combination. Greedy gave us an optimal solution in polynomial time — exactly the kind of win you want from an algorithm.