# Activity selection problem

The **activity selection problem** is a mathematical optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time (s_{i}) and finish time (f_{i}). The problem is to select the maximum number of activities that can be performed by a single person or machine, assuming that a person can only work on a single activity at a time.

A classic application of this problem is in scheduling a room for multiple competing events, each having its own time requirements (start and end time), and many more arise within the framework of operations research.

Assume there exist *n* activities with each of them being represented by a start time *s _{i}* and finish time

*f*. Two activities

_{i}*i*and

*j*are said to be non-conflicting if

*s*≥

_{i}*f*or

_{j}*s*≥

_{j}*f*. The activity selection problem consists in finding the maximal solution set (S) of non-conflicting activities, or more precisely there must exist no solution set S’ such that |S’| > |S|. In the case that multiple maximal solutions have equal sizes.

_{i}The activity selection problem is notable in that using a greedy algorithm to find a solution will always result in an optimal solution. A pseudocode sketch of the algorithm and a proof of the optimality of its result are included below.

### Algorithm

- Sort the set of activities by finishing time (f[i])
- S = {1}
- f = f[1]
**for**i=2 to n**if**s[i] ≥ f- S = S U i
- f = f[i]

**endfor**

### Proof of optimality

Let S = {1, 2, . . ., n} be the set of activities ordered by finish time. Thus activity 1 has the earliest finish time.

Suppose, A is a subset of S is an optimal solution and let activities in A be ordered by finish time. Suppose, the first activity in A is k.

If k = 1, then A begins with greedy choice and we are done (or to be very precise, there is nothing to prove here).

If k not=1, we want to show that there is another solution B that begins with greedy choice, activity 1.

Let B = (A – {k}) U {1}. Because f[1] =< f[k], the activities in B are disjoint and since B has same number of activities as A, i.e., |A| = |B|, B is also optimal.

Once the greedy choice is made, the problem reduces to finding an optimal solution for the subproblem. If A is an optimal solution to the original problem S, then A` = A – {1} is an optimal solution to the activity-selection problem S` = {i in S: s[i] >= f[1]}.

Why? If we could find a solution B` to S` with more activities then A`, adding 1 to B` would yield a solution B to S with more activities than A, there by contradicting the optimality.