Weighted Interval Scheduling

 Introduction

Weighted interval scheduling is a variant of the Interval scheduling problem described under chapter 16 of our CLRS book [1]. If you are not familiar with the Interval scheduling problem, I would encourage you to read that in the book [1], before proceeding with the rest of this article. Recall that in the original problem we are given a set of $n$ activities, each with associated start time $s_i$ and finish time $f_i$. Our objective is to find the maximum subset of non-overlapping activities. Moreover, the problem of finding the maximum subset of compatible activities exhibits the greedy choice property. Now with this information in mind, let’s move on to our new variant.

 

Problem Statement

Exercise 16.1-5

Consider a modification to the activity-selection problem in which each activity $a_i$ has, in addition to start and finish time, a value $v_i$. The objective is no longer to maximize the number of activities scheduled, but instead to maximize the total value of the activities scheduled. That is, we wish to choose a set $A$ of compatible activities such that $\Large \sum_{a_k \in A}v_k$ is maximized. Give a polynomial-time algorithm for this problem. [1]

Weighted Interval Scheduling - Definition

Note that this variant of the problem does not exhibit the greedy choice property [1], thus, we use dynamic programming to solve this problem.

Let $s$, $f$ and $v$ be arrays representing start, finish times and the profit which we can obtain from each of these activities respectively. Let $p[1 \ldots n]$ be an array representing maximum profit of each subproblem of size $1 \ldots n$. Let $k$ be the current activity being considered and let $c$ be the last activity which is compatible with activity $k$. Let $p[k]$ be the maximum profit which we can obtain using the first $k$ activities, i.e. a subproblem of size $k$. Here’s our recurrence for the weighted interval scheduling problem.

$$p[k] = max(p[k - 1],\; p[c] + v_k)$$

 

Weighted Interval Scheduling - Approach

Let’s sort the arrays $s$, $f$ and $v$ based on the monotone increasing order of finish times of the activities first. Now, we have two choices. We can dispense the current activity $a_k$ and get the profit $p[k - 1]$, which is the maximum profit we can attain without the activity $a_k$ to the set of first $k$ activities. And then, the optimal profit we can obtain by including the activity $a_k$ in our solution is, $v_k + p[c]$, such that $c$ is the last activity which is compatible with activity $a_k$. The maximum value of the above two, yields an optimal solution. We can find the value of $c$, by performing a binary search over the array $f$ using the $s_k$ as an argument to the function. In fact, we need to find the binary predecessor of $s_k$ in the array $f$ using a closed interval. The algorithm that follows, implements this idea.

**Input:** activity start and finish time arrays $s$, $f$ and array $v-$ the value of each activity.  
**Output:** Table $p$, which contains the maximum attainable profit for each subproblem of size $1 \ldots n$.  
$WEIGHTED-INTERVAL-SCHEDULING(s, f, v, a)$              
$\phantom{{}++{}}$ sort the arrays $s$, $f$ and $v$ in monotone increasing order of finish times     
$\phantom{{}++{}}$ rearrange the activity numbers/identifiers in array $a$      
$\phantom{{}++{}}$ let $p[1 \ldots n]$ be a new array  
$\phantom{{}++{}}$ $p[1] \gets v[1]$    
$\phantom{{}++{}}$ let $n = f.length$   
$\phantom{{}++{}}$ `for` $k = 2$ to $n$   
$\phantom{{}++{}}$$\phantom{{}++{}}$ let $c \gets PREDECESSOR(f,\; s[k] + 1)$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ let $cv \gets 0$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ `if` $c \gt 0$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $cv \gets p[c]$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ $p[k] \gets max(p[k - 1],\; cv + v[k])$         
$\phantom{{}++{}}$ return $p$

**Input:** array $a$ sorted in monotone increasing order and target value $t$.  
**Output:** Position of the predecessor of $t$ in array $a$.   
$PREDECESSOR(a, t)$     
$\phantom{{}++{}}$ let $l \gets 1$  
$\phantom{{}++{}}$ let $r \gets a.length + 1$  
$\phantom{{}++{}}$ `while` $l \lt r$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ let $mid \gets \lfloor (l + r) / 2\rfloor$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ `if` $a[mid] \lt target$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $l \gets mid + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ `else`  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $r \gets mid$  
$\phantom{{}++{}}$ return l - 1 

Constructing an optimal solution

Now, let’s use the table $p$ computed at the previous step to find the activities that are in our optimal solution. Note that we have used an array $a$ just to store initial activity numbers, since after the sorting in place, we lose those initial ordering of elements. Thus, for each activity, we keep it’s initial number in $a$ so that we can find it’s initial number easily while finding the activities that are in our optimal solution. If you just need to find the maximum profit which we can obtain out of these activities, without finding the actual activities in an optimal solution, then you can merely dispense with this array $a$.  

Let $r$ be the remaining profit, and it is initialized to $p[n]$. We start at the position $n - 1$ and go down. At each step $i$, if the current profit $p[i]$ is less than the remaining profit, then we take the item that immediately follows the current item, print it, and reduce it’s worth from the remaining profit value. Here’s our algorithm for finding an optimal solution.

**Input:** activity values array $v$, profit table $p$ and activity numbers $a$   
$FIND-ACTIVITIES(v, p, a)$     
$\phantom{{}++{}}$ let $n \gets v.length$  
$\phantom{{}++{}}$ let $i \gets n - 1$  
$\phantom{{}++{}}$ let $r \gets p[n]$  
$\phantom{{}++{}}$ `while` $i \gt 0$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ `if` $p[i] \lt r$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ print $a[i + 1]$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $r \gets r - v[i + 1]$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ $i \gets i - 1$  
$\phantom{{}++{}}$ `if` $r \gt 0$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ print a[1]

Sample Implementation

Here’s our implementation for solving the problem of weighted interval scheduling. Also note that we are basing our implementation off of zero based indices on the contrary to the one based indices used in the pseudocode above. For some reason, if your programming language supports one based indices such as Fortran or Smalltalk, then consider implementing the above pseudocode as it is.

 

Analysis

Our approach of finding the non-overlapping activities which yields the maximum profit involves $n \cdot log_2(n)$ worst case running time and $O(n)$ space for storing profit values in the array $p$. Note that, in the worst case, for each activity $k$, we perform a binary search over an $n$ element sorted array, which incurs us $O(log_2\; n)$ time at each iteration of the for loop. 

Our approach of constructing an optimal solution takes $O(n)$ time complexity along with $O(1)$ constant space. 

 

References

[1] https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844