Activity Selection
Choose the maximum number of non-overlapping activities. Sorting by finish time and always taking the earliest-finishing compatible activity is provably optimal.
- Category
- Greedy
- Time complexity
- O(n log n)
- Space complexity
- O(1)
Pseudocode
sort activities by finish time take the first activity skip any that overlap the last taken take the next compatible one
Reference implementation
acts.sort(key=lambda a: a.end)
last = -inf
for s, e in acts:
if s >= last:
take(s, e); last = e