Activity selection problem

Formal definition

Assume there exist n activities with each of them being represented by a start time s_i and finish time f_i. Two activities i and j are said to be non-conflicting if s_i ≥ f_j or s_j ≥ f_i. 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.

Optimal Solution

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.

Explanation

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.

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 by using the finish times stored in the array f . This operation can be done in O ( n ⋅ log 2 ⁡ n ) time, using for example merge sort, heap sort, or quick sort algorithms.

Line 5: Creates a set S to store the selected activities, and initialises it with the first activity A [ 1 ] . Note that, since the A has already been sorted according to the finish times in f , A [ 1 ] is the activity with the smallest finish time.

Line 6: Creates a variable k that keeps track of the index of the last selected activity.

Line 10: Starts iterating from the second element of that array A up to its last element.

Line 11: If the start time s [ i ] of the i t h activity ( A [ i ] ) is greater or equal to the finish time f [ k ] of the last selected activity ( A [ k ] ), then A [ i ] is compatible to the selected activities in the set S , and thus it can be added to S ; this is what is done in line 12.

Line 13: The index of the last selected activity is updated to the just added activity A [ i ] .

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 and is an optimal solution, and let activities in A be ordered by finish time. Suppose that the first activity in A is k ≠ 1, that is, this optimal solution does not start with the "greedy choice." We want to show that there is another solution B that begins with the greedy choice, activity 1.

Let B = ( A ∖ { k } ) ∪ { 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 ∈ 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, contradicting the optimality.

Weighted Activity Selection Problem

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:

Consider an optimal solution containing activity k. We now have non-overlapping activities on the left and right of k. We can recursively find solutions for these two sets because of optimal sub-structure. As we don't know k, we can try each of the activities. This approach leads to an O ( n 3 ) solution. This can be optimized further considering that for each set of activities in ( i , j ) , we can find the optimal solution if we had known the solution for ( i , t ) , where t is the last non-overlapping interval with j in ( i , j ) . This yields an O ( n 2 ) solution. This can be further optimized considering the fact that we do not need to consider all ranges ( i , j ) but instead just ( 1 , j ) . The following algorithm thus yields an O ( n log ⁡ n ) solution: