Activity selection problem

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.

Algorithm

<span id="mwLw"></span><span class="linenos" data-line="1" id="mwMA"></span><span class="n" id="mwMQ">Greedy</span><span class="o" id="mwMg">-</span><span class="n" id="mwMw">Iterative</span><span class="o" id="mwNA">-</span><span class="n" id="mwNQ">Activity</span><span class="o" id="mwNg">-</span><span class="n" id="mwNw">Selector</span><span class="p" id="mwOA">(</span><span class="n" id="mwOQ">A</span><span class="p" id="mwOg">,</span><span class="w" id="mwOw"> </span><span class="n" id="mwPA">s</span><span class="p" id="mwPQ">,</span><span class="w" id="mwPg"> </span><span class="n" id="mwPw">f</span><span class="p" id="mwQA">)</span><span class="o" id="mwQQ">:</span><span class="w" id="mwQg"> </span> <span class="linenos" data-line="2" id="mwQw"></span> <span class="linenos" data-line="3" id="mwRA"></span><span class="w" id="mwRQ"> </span><span class="n" id="mwRg">Sort</span><span class="w" id="mwRw"> </span><span class="n" id="mwSA">A</span><span class="w" id="mwSQ"> </span><span class="n" id="mwSg">by</span><span class="w" id="mwSw"> </span><span class="n" id="mwTA">finish</span><span class="w" id="mwTQ"> </span><span class="n" id="mwTg">times</span><span class="w" id="mwTw"> </span><span class="n" id="mwUA">stored</span><span class="w" id="mwUQ"> </span><span class="n" id="mwUg">in</span><span class="w" id="mwUw"> </span><span class="n" id="mwVA">f</span> <span class="linenos" data-line="4" id="mwVQ"></span><span class="w" id="mwVg"> </span><span class="n" id="mwVw">S</span><span class="w" id="mwWA"> </span><span class="o" id="mwWQ">=</span><span class="w" id="mwWg"> </span><span class="p" id="mwWw">{</span><span class="n" id="mwXA">A</span><span class="p" id="mwXQ">[</span><span class="mi" id="mwXg">1</span><span class="p" id="mwXw">]}</span><span class="w" id="mwYA"> </span> <span class="linenos" data-line="5" id="mwYQ"></span><span class="w" id="mwYg"> </span><span class="n" id="mwYw">k</span><span class="w" id="mwZA"> </span><span class="o" id="mwZQ">=</span><span class="w" id="mwZg"> </span><span class="mi" id="mwZw">1</span> <span class="linenos" data-line="6" id="mwaA"></span><span class="w" id="mwaQ"> </span> <span class="linenos" data-line="7" id="mwag"></span><span class="w" id="mwaw"> </span><span class="n" id="mwbA">n</span><span class="w" id="mwbQ"> </span><span class="o" id="mwbg">=</span><span class="w" id="mwbw"> </span><span class="n" id="mwcA">A</span><span class="p" id="mwcQ">.</span><span class="n" id="mwcg">length</span> <span class="linenos" data-line="8" id="mwcw"></span><span class="w" id="mwdA"> </span> <span class="linenos" data-line="9" id="mwdQ"></span><span class="w" id="mwdg"> </span><span class="k" id="mwdw">for</span><span class="w" id="mweA"> </span><span class="n" id="mweQ">i</span><span class="w" id="mweg"> </span><span class="o" id="mwew">=</span><span class="w" id="mwfA"> </span><span class="mi" id="mwfQ">2</span><span class="w" id="mwfg"> </span><span class="n" id="mwfw">to</span><span class="w" id="mwgA"> </span><span class="n" id="mwgQ">n</span><span class="o" id="mwgg">:</span> <span class="linenos" data-line="10" id="mwgw"></span><span class="w" id="mwhA"> </span><span class="k" id="mwhQ">if</span><span class="w" id="mwhg"> </span><span class="n" id="mwhw">s</span><span class="p" id="mwiA">[</span><span class="n" id="mwiQ">i</span><span class="p" id="mwig">]</span><span class="w" id="mwiw"> </span><span class="err" id="mwjA">≥</span><span class="w" id="mwjQ"> </span><span class="n" id="mwjg">f</span><span class="p" id="mwjw">[</span><span class="n" id="mwkA">k</span><span class="p" id="mwkQ">]</span><span class="o" id="mwkg">:</span><span class="w" id="mwkw"> </span> <span class="linenos" data-line="11" id="mwlA"></span><span class="w" id="mwlQ"> </span><span class="n" id="mwlg">S</span><span class="w" id="mwlw"> </span><span class="o" id="mwmA">=</span><span class="w" id="mwmQ"> </span><span class="n" id="mwmg">S</span><span class="w" id="mwmw"> </span><span class="n" id="mwnA">U</span><span class="w" id="mwnQ"> </span><span class="p" id="mwng">{</span><span class="n" id="mwnw">A</span><span class="p" id="mwoA">[</span><span class="n" id="mwoQ">i</span><span class="p" id="mwog">]}</span> <span class="linenos" data-line="12" id="mwow"></span><span class="w" id="mwpA"> </span><span class="n" id="mwpQ">k</span><span class="w" id="mwpg"> </span><span class="o" id="mwpw">=</span><span class="w" id="mwqA"> </span><span class="n" id="mwqQ">i</span> <span class="linenos" data-line="13" id="mwqg"></span><span class="w" id="mwqw"> </span> <span class="linenos" data-line="14" id="mwrA"></span><span class="w" id="mwrQ"> </span><span class="k" id="mwrg">return</span><span class="w" id="mwrw"> </span><span class="n" id="mwsA">S</span>

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.

• ${\displaystyle A}$ is an array containing the activities.
• ${\displaystyle s}$ is an array containing the start times of the activities in ${\displaystyle A}$.
• ${\displaystyle f}$ is an array containing the finish times of the activities in ${\displaystyle 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 ${\displaystyle A}$ by using the finish times stored in the array ${\displaystyle f}$. This operation can be done in ${\displaystyle O(n\cdot \log n)}$ time, using for example merge sort, heap sort, or quick sort algorithms.

Line 4: Creates a set ${\displaystyle S}$ to store the selected activities, and initialises it with the activity ${\displaystyle A[1]}$ that has the earliest finish time.

Line 5: Creates a variable ${\displaystyle k}$ that keeps track of the index of the last selected activity.

Line 9: Starts iterating from the second element of that array ${\displaystyle A}$ up to its last element.

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

Line 12: The index of the last selected activity is updated to the just added activity ${\displaystyle A[i]}$.

Proof of optimality

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

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 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 ${\displaystyle O(n^3)}$ solution. This can be optimized further considering that for each set of activities in ${\displaystyle (i,j)}$, we can find the optimal solution if we had known the solution for ${\displaystyle (i,t)}$, where t is the last non-overlapping interval with j in ${\displaystyle (i,j)}$. This yields an ${\displaystyle O(n^2)}$ solution. This can be further optimized considering the fact that we do not need to consider all ranges ${\displaystyle (i,j)}$ but instead just ${\displaystyle (1,j)}$. The following algorithm thus yields an ${\displaystyle O(n\log n)}$ solution:

<span id="mwARQ"></span><span class="linenos" data-line="1" id="mwARU"></span><span class="n" id="mwARY">Weighted</span><span class="o" id="mwARc">-</span><span class="n" id="mwARg">Activity</span><span class="o" id="mwARk">-</span><span class="n" id="mwARo">Selection</span><span class="p" id="mwARs">(</span><span class="n" id="mwARw">S</span><span class="p" id="mwAR0">)</span><span class="o" id="mwAR4">:</span><span class="w" id="mwAR8"> </span><span class="c1" id="mwASA">// S = list of activities</span> <span class="linenos" data-line="2" id="mwASE"></span> <span class="linenos" data-line="3" id="mwASI"></span><span class="w" id="mwASM"> </span><span class="n" id="mwASQ">sort</span><span class="w" id="mwASU"> </span><span class="n" id="mwASY">S</span><span class="w" id="mwASc"> </span><span class="n" id="mwASg">by</span><span class="w" id="mwASk"> </span><span class="n" id="mwASo">finish</span><span class="w" id="mwASs"> </span><span class="n" id="mwASw">time</span> <span class="linenos" data-line="4" id="mwAS0"></span><span class="w" id="mwAS4"> </span><span class="n" id="mwAS8">opt</span><span class="p" id="mwATA">[</span><span class="mi" id="mwATE">0</span><span class="p" id="mwATI">]</span><span class="w" id="mwATM"> </span><span class="o" id="mwATQ">=</span><span class="w" id="mwATU"> </span><span class="mi" id="mwATY">0</span><span class="w" id="mwATc"> </span><span class="c1" id="mwATg">// opt[j] represents optimal solution (sum of weights of selected activities) for S[1,2..,j]</span> <span class="linenos" data-line="5" id="mwATk"></span><span class="w" id="mwATo"> </span> <span class="linenos" data-line="6" id="mwATs"></span><span class="w" id="mwATw"> </span><span class="k" id="mwAT0">for</span><span class="w" id="mwAT4"> </span><span class="n" id="mwAT8">i</span><span class="w" id="mwAUA"> </span><span class="o" id="mwAUE">=</span><span class="w" id="mwAUI"> </span><span class="mi" id="mwAUM">1</span><span class="w" id="mwAUQ"> </span><span class="n" id="mwAUU">to</span><span class="w" id="mwAUY"> </span><span class="n" id="mwAUc">n</span><span class="o" id="mwAUg">:</span> <span class="linenos" data-line="7" id="mwAUk"></span><span class="w" id="mwAUo"> </span><span class="n" id="mwAUs">t</span><span class="w" id="mwAUw"> </span><span class="o" id="mwAU0">=</span><span class="w" id="mwAU4"> </span><span class="n" id="mwAU8">binary</span><span class="w" id="mwAVA"> </span><span class="n" id="mwAVE">search</span><span class="w" id="mwAVI"> </span><span class="n" id="mwAVM">to</span><span class="w" id="mwAVQ"> </span><span class="n" id="mwAVU">find</span><span class="w" id="mwAVY"> </span><span class="n" id="mwAVc">activity</span><span class="w" id="mwAVg"> </span><span class="n" id="mwAVk">with</span><span class="w" id="mwAVo"> </span><span class="n" id="mwAVs">finish</span><span class="w" id="mwAVw"> </span><span class="n" id="mwAV0">time</span><span class="w" id="mwAV4"> </span><span class="o" id="mwAV8"><=</span><span class="w" id="mwAWA"> </span><span class="n" id="mwAWE">start</span><span class="w" id="mwAWI"> </span><span class="n" id="mwAWM">time</span><span class="w" id="mwAWQ"> </span><span class="k" id="mwAWU">for</span><span class="w" id="mwAWY"> </span><span class="n" id="mwAWc">i</span> <span class="linenos" data-line="8" id="mwAWg"></span><span class="w" id="mwAWk"> </span><span class="c1" id="mwAWo">// if there are more than one such activities, choose the one with last finish time</span> <span class="linenos" data-line="9" id="mwAWs"></span><span class="w" id="mwAWw"> </span><span class="n" id="mwAW0">opt</span><span class="p" id="mwAW4">[</span><span class="n" id="mwAW8">i</span><span class="p" id="mwAXA">]</span><span class="w" id="mwAXE"> </span><span class="o" id="mwAXI">=</span><span class="w" id="mwAXM"> </span><span class="n" id="mwAXQ">MAX</span><span class="p" id="mwAXU">(</span><span class="n" id="mwAXY">opt</span><span class="p" id="mwAXc">[</span><span class="n" id="mwAXg">i</span><span class="mi" id="mwAXk">-1</span><span class="p" id="mwAXo">],</span><span class="w" id="mwAXs"> </span><span class="n" id="mwAXw">opt</span><span class="p" id="mwAX0">[</span><span class="n" id="mwAX4">t</span><span class="p" id="mwAX8">]</span><span class="w" id="mwAYA"> </span><span class="o" id="mwAYE">+</span><span class="w" id="mwAYI"> </span><span class="n" id="mwAYM">w</span><span class="p" id="mwAYQ">(</span><span class="n" id="mwAYU">i</span><span class="p" id="mwAYY">))</span> <span class="linenos" data-line="10" id="mwAYc"></span><span class="w" id="mwAYg"> </span> <span class="linenos" data-line="11" id="mwAYk"></span><span class="w" id="mwAYo"> </span><span class="k" id="mwAYs">return</span><span class="w" id="mwAYw"> </span><span class="n" id="mwAY0">opt</span><span class="p" id="mwAY4">[</span><span class="n" id="mwAY8">n</span><span class="p" id="mwAZA">]</span>