Problem:
In many situations, we need to share a single resource among competing activities. Such resource could be an individual person, a classroom, a processor, etc. The goal is to satisfy as many activities as possible. This leads to the activity selection problem:

There are a set of activities. Each activity has a start time and a finish time . To satisfy activity , the resource must be allocated to during time interval [, ). Two activities are said compatible if their time intervals do not intersect. Our task is to find out a maximum subset of mutually compatible activities.

Algorithm

A natural greedy strategy is to incrementally grow the subset by try putting in compatible activities. To use this strategy, the activities should have an order so that they can be tried one by one. Interestingly, an increasing order of finish times will lead to optimal solution (while other orderings, such as ordering in start times, will not). The algorithm is presented as follows.

Activity-Selection

Correctness:
It is non-trivial to see why the greedy strategy works. The following lemma will provide some insight into the algorithm.

Lemma 1:  Suppose Activity-Selection selects n activities with finish time and some optimal algorithm OPT selects m activities with finish time . Then for any ,.

Proof:
This lemma could be proved by induction. First note that equals the earliest finish time among all activities, so the basis case holds. Next assume that holds. Denote the k-th activity selected by Opt as and let s be ’s start time. Then there is . Since , A_k must be also compatible with the previous k-1 activities selected by Activity-Selection. So the k-th activity selected by Activity-Selection will have its finish time no greater than ’s finish time (otherwise Activity-Selection would rather select ). And this shows that .

Theorem 2: Activity-Selection selects a maximum subset of activities.
Following Lemma 1, assume , then the m-th activity selected by Opt with start time is still compatible with all the n activities selected by Activity-Selection. So Activity-Selection will be able to satisfy at least n+1 activities, which forms a contradiction.

Time Complexity:
To implement Activity-Selection, we first sort all activities according to their finish times. This takes O(n log n) time. The incremental subset construction takes O(n) time. So the overall time complexity is dominated by the sorting phase and is O(n log n).

Space Complexity:
The storage of start time, finish time and subset S all take O(n) space. The space requirement of sorting phase depends on chosen sorting algorithm yet will not exceed O(n). So the overall space complexity is O(n).

Pseudo Code

sort all activities so that f(A[1]) ≤ … ≤ f(A[n])
S = { 1 }
k = 1
for i = 2 to n
	if f(A[i]) ≥ s(A[k])
		add i into S
		k = i
return  S
        

Other references:

[1] http://en.wikipedia.org/wiki/Activity_selection_problem
[2] http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/actSelectionGreedy.htm
[3] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press, Massachusetts,  2001.