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.
There's also a recursive version of this greedy algorithm.
Line 3: Sorts in increasing order of finish times the array of activities
by using the finish times stored in the array
that has the earliest finish time.
that keeps track of the index of the last selected activity.
Line 9: Starts iterating from the second element of that array
Lines 10,11: If the start time
) is greater or equal to the finish time
is compatible to the selected activities in the set
be the set of activities ordered by finish time.
is an optimal solution, also ordered by finish time; and that the index of the first activity in A is
, i.e., this optimal solution does not start with the greedy choice.
, which begins with the greedy choice (activity 1), is another optimal solution.
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
is an optimal solution to the activity-selection problem
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 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.