# Activity selection problem

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Activity_selection_problem
> Markdown URL: https://mediated.wiki/source/Activity_selection_problem.md
> Source: https://en.wikipedia.org/wiki/Activity_selection_problem
> Source revision: 1302530372
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Combinatorial optimization problem}}
{{More citations needed|date=January 2021}}
The '''activity selection problem'''  is a [combinatorial optimization](/source/combinatorial_optimization) problem concerning the selection of non-conflicting [activities](/source/task_(project_management)) to perform within a given [time frame](/source/time_frame), given a set of activities each marked by a start time (s<sub>i</sub>) and finish time (f<sub>i</sub>). The problem is to select the maximum number of activities that can be performed by a single person or [machine](/source/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)](/source/Interval_scheduling), which is a special type of the more general [Interval Scheduling](/source/Interval_scheduling) problem.

A classic application of this problem is in scheduling a room for multiple [competing](/source/competing) events, each having its own time requirements (start and end time), and many more arise within the framework of [operations research](/source/operations_research).

==Formal definition==
Assume there exist ''n'' activities with each of them being represented by a start time ''s<sub>i</sub>'' and finish time ''f<sub>i</sub>''. Two activities ''i'' and ''j'' are said to be non-conflicting if ''s<sub>i</sub>'' ≥ ''f<sub>j</sub>'' or ''s<sub>j</sub>'' ≥ ''f<sub>i</sub>''. 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](/source/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](/source/greedy_algorithm) to find a solution will always result in an [optimal solution](/source/optimal_solution). A [pseudocode](/source/pseudocode) sketch of the iterative version of the algorithm and a proof of the optimality of its result are included below.

===Algorithm===

<syntaxhighlight lang="c" line>
Greedy-Iterative-Activity-Selector(A, s, f): 

    Sort A by finish times stored in f
    S = {A[1]} 
    k = 1
    
    n = A.length
    
    for i = 2 to n:
        if s[i] ≥ f[k]: 
            S = S U {A[i]}
            k = i
    
    return S
</syntaxhighlight>

==== 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.
*<math>A</math> is an array containing the ''activities''. 
* <math>s</math> is an array containing the ''start times'' of the activities in <math>A</math>.
* <math>f</math>  is an array containing the ''finish times'' of the activities in <math>A</math>.

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

'''Line 4:''' Creates a set <math>S</math> to store the ''selected activities'', and initialises it with the activity <math>A[1]</math> that has the earliest finish time.

'''Line 5:''' Creates a variable <math>k</math> that keeps track of the index of the last selected activity.

'''Line 9:''' Starts iterating from the second element of that array <math>A</math> up to its last element.

'''Lines 10,11:''' If the ''start time'' <math>s[i]</math> of the <math>ith</math> activity (<math>A[i]</math>) is greater or equal to the ''finish time'' <math>f[k]</math> of the ''last selected activity'' (<math>A[k]</math>), then <math>A[i]</math> is compatible to the selected activities in the set <math>S</math>, and thus it can be added to <math>S</math>.

'''Line 12:''' The index of the last selected activity is updated to the just added activity <math>A[i]</math>.

===Proof of optimality===
Let <math>S = \{1, 2, \ldots , n\}</math> be the set of activities ordered by finish time. Assume that <math>A\subseteq S</math> is an optimal solution, also ordered by finish time; and that the index of the first activity in ''A'' is <math>k\neq 1</math>, i.e., this optimal solution ''does not'' start with the greedy choice. We will show that <math>B = (A \setminus \{k\}) \cup \{1\}</math>, which begins with the greedy choice (activity 1), is another optimal solution. Since <math>f_1 \leq f_k</math>, and the activities in A are [disjoint](/source/Disjoint_sets) by definition, the activities in B are also disjoint. Since ''B'' has the same number of activities as ''A'', that is, <math>|A| = |B|</math>, ''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'' containing the greedy choice, then <math>A^\prime = A \setminus \{1\}</math> is an optimal solution to the activity-selection problem <math>S' = \{i \in S: s_i \geq f_1\}</math>.

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.

===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](/source/dynamic_programming) solution can readily be formed using the following approach:<ref>[http://www.cs.princeton.edu/~wayne/cs423/lectures/dynamic-programming-4up.pdf Dynamic Programming with introduction to Weighted Activity Selection]</ref>

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

<syntaxhighlight lang="c" line="1">
Weighted-Activity-Selection(S):  // S = list of activities

    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]
</syntaxhighlight>

==References==
{{Reflist}}

==External links==
* [http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/actSelectionGreedy.htm Activity Selection Problem]

Category:Optimal scheduling
Category:Articles containing proofs

---
Adapted from the Wikipedia article [Activity selection problem](https://en.wikipedia.org/wiki/Activity_selection_problem) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Activity_selection_problem?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.