Activity Selection

Problem

Given n activities with start and finish times, select maximum number of non-overlapping activities. Activities compatible if one finishes before other starts.

Greedy Choice

Earliest finish time is optimal. Sort by finish time. Pick first, then repeatedly pick next compatible (starts after last picked finishes). Intuition: leaving more room for remaining activities.

Implementation

Proof of Correctness

Exchange argument: Let G be greedy solution, O optimal. First activity in G finishes earliest. If O's first differs, swap it with G's first (still valid, finishes no later). Repeat for remaining activities. G matches O in size.