Activity Selection
You are given n activities, each with a start and finish time, and a single resource that can host one activity at a time. Select the maximum number of activities that do not overlap in time.
- 1 ≤ n ≤ 10^5
- 0 ≤ start < finish ≤ 10^9
- Maximum number of compatible intervals
- Picking the activity that finishes earliest leaves the most room
- Sort by finish time, single pass
When a locally best choice (earliest finish time, largest ratio, farthest reach) can be proved never to hurt the global optimum, you can commit to it without exploring alternatives and get O(n log n) from sorting. The proof usually comes via an exchange argument; if you cannot sketch one, suspect DP instead.
Sort activities by finish time. Take the first one, then scan the rest and select each activity whose start is at least the finish time of the last selected one. The exchange argument shows that any optimal solution can be rewritten to begin with the earliest-finishing activity without losing a selection, so the greedy choice is safe at every step.
- Sorting by start time or by duration are both wrong. Weighted activity selection needs DP with binary search in O(n log n).