Activity Selection

Difficulty: Easy · Topic: Greedy algorithms

Given activities as [start, end] intervals, return the maximum number you can attend if you can only do one at a time. The greedy rule: sort by finish time and take each activity whose start is ≥ the last selected finish.

Examples

max_activities([[1,3],[2,5],[4,7],[1,8],[5,9],[8,10]])
→ 3

[1,3], [4,7], [8,10].

max_activities([[1,2],[2,3],[3,4]])
→ 3

Target complexity: time O(n log n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.