The activity selection problem is a combinatorial 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 (si) and finish time (fi). 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. The activity selection problem is also known as the Interval scheduling maximization problem (ISMP), which is a special type of the more general Interval Scheduling problem.
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 si and finish time fi. Two activities i and j are said to be non-conflicting if si ≥ fj or sj ≥ fi. 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.
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 iterative version of the algorithm and a proof of the optimality of its result are included below.
Sort A by finish times stored in f S = k = 1 n = A.length for i = 2 to n: if s[i] ≥ f[k]: S = S U k = i return S
Line 1: This algorithm is called Greedy-Iterative-Activity-Selector, because it is first of all a greedy algorithm, and then it is iterative. There's also a recursive version of this greedy algorithm.
A
s
A
f
A
Note that these arrays are indexed starting from 1 up to the length of the corresponding array.
Line 3: Sorts in increasing order of finish times the array of activities
A
f
O(n ⋅ logn)
Line 4: Creates a set
S
A[1]
Line 5: Creates a variable
k
Line 9: Starts iterating from the second element of that array
A
Lines 10,11: If the start time
s[i]
ith
A[i]
f[k]
A[k]
A[i]
S
S
Line 12: The index of the last selected activity is updated to the just added activity
A[i]
Let
S=\{1,2,\ldots,n\}
A\subseteqS
k ≠ 1
B=(A\setminus\{k\})\cup\{1\}
f1\leqfk
|A|=|B|
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 containing the greedy choice, then
A\prime=A\setminus\{1\}
S'=\{i\inS:si\geqf1\}
Why? If this were not the case, pick a solution B′ to S′ with more activities than A′ containing the greedy choice for S′. Then, adding 1 to B′ would yield a feasible solution B to S with more activities than A, contradicting the optimality.
The generalized version of the activity selection problem involves selecting an optimal set of non-overlapping activities such that the total weight is maximized. Unlike the unweighted version, there is no greedy solution to the weighted activity selection problem. However, a dynamic programming solution can readily be formed using the following approach:[1]
Consider an optimal solution containing activity . We now have non-overlapping activities on the left and right of . We can recursively find solutions for these two sets because of optimal sub-structure. As we don't know, we can try each of the activities. This approach leads to an
O(n3)
(i,j)
(i,t)
(i,j)
O(n2)
(i,j)
(1,j)
O(nlogn)
sort S by finish time opt[0] = 0 // opt[j] represents optimal solution (sum of weights of selected activities) for S[1,2..,j] for i = 1 to n: t = binary search to find activity with finish time <= start time for i // if there are more than one such activities, choose the one with last finish time opt[i] = MAX(opt[i-1], opt[t] + w(i)) return opt[n]