Activity selection problem

The activity selection problem deals with 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.

Formal definition

We are given n activities with each of them being represented by a start time s_i and finish time f_i. Also, two activities i and j are said to be non-conflicting if s_i ≥ f_j or s_j ≥ f_i. We are required to find the maximum set (S) of non-conflicting activities. There does not exist a solution set S' for this problem such that |S'| > |S|.

Greedy algorithm

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

Proof

Let S = {1, 2, . . . , n} be the set of activities. Since activities are in order by finish time. It implies that activity 1 has the earliest finish time. Suppose, A is a subset of S is an optimal solution and let activities in A are 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 f1 =< fk, 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 problem. 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: Si >= fi}.

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.

External links

• Activity Selection Problem