Activity Selection

Why Greedy Works

Greedy Choice Property holds: picking the activity with the earliest finish time leaves the most room for the rest. Optimal Substructure: after choosing one activity, the remaining problem is the same on the filtered intervals.

Algorithm Steps

1. Sort activities by increasing finish time.
2. Initialize lastFinish = -∞.
3. Scan in order; choose activity if start ≥ lastFinish, then update lastFinish.
4. Otherwise, skip the activity.

Pseudocode

1procedure ACTIVITY_SELECTION(intervals)
2  sort intervals by increasing finish time
3  lastFinish ← −∞
4  chosen ← ∅
5  for each interval (s, f) in intervals do
6    if s ≥ lastFinish then
7      add interval to chosen
8      lastFinish ← f
9    else
10      skip interval
11    end if
12  end for
13  return chosen
14end procedure