The activity selection problem is a
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
problem concerning the selection of non-conflicting
activities to perform within a given
time frame
Time is the continued sequence of existence and events that occurs in an apparently irreversible succession from the past, through the present, into the future. It is a component quantity of various measurements used to sequence events, to c ...
, 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
A machine is a physical system using Power (physics), power to apply Force, forces and control Motion, movement to perform an action. The term is commonly applied to artificial devices, such as those employing engines or motors, but also to na ...
, 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
Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an ''interval'' describing the time in which it needs to be processed b ...
problem.
A classic application of this problem is in scheduling a room for multiple
competing
Competition is a rivalry where two or more parties strive for a common goal which cannot be shared: where one's gain is the other's loss (an example of which is a zero-sum game). Competition can arise between entities such as organisms, indivi ...
events, each having its own time requirements (start and end time), and many more arise within the framework of
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
.
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
In mathematics, a solution set is the set of values that satisfy a given set of equations or inequalities.
For example, for a set of polynomials over a ring ,
the solution set is the subset of on which the polynomials all vanish (evaluate to ...
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
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
to find a solution will always result in an
optimal solution
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
. A
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
sketch of the iterative version of the algorithm and a proof of the optimality of its result are included below.
Algorithm
Greedy-Iterative-Activity-Selector(A, s, f):
Sort A by finish times stored in f
S =
k = 1
n = A.length
for i = 2 to n:
if s ≥ f
S = S U
k = i
return S
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.
*
is an array containing the ''activities''.
*
is an array containing the ''start times'' of the activities in
.
*
is an array containing the ''finish times'' of the activities in
.
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
by using the finish times stored in the array
. This operation can be done in
time, using for example merge sort, heap sort, or quick sort algorithms.
Line 4: Creates a set
to store the ''selected activities'', and initialises it with the activity