Activity Selection Problem

A problem for which a greedy algorithm does work and gives the optimal solution is the activity selection problem. There is a weighted version of the same problem, discussed here, which cannot be solved using a greedy algorithm. However, its unweighted version that we discuss here can be solved optimally using a greedy strategy.

The activity selection problem involves a set of n activities, each having a start and finish time. Some of these activities are overlapping. The objective is to select a maximum sized set of non-overlapping activities.

The following are the parameters of this problem:

1. n is the total number of intervals
2. Array s and f of size n to store the start and finish time of each activity
3. s[j] < f[j] for j = 0..(n-1)
4. The arrays are sorted according to finish time values (in f array) in ascending order