33 The Weighted Interval Scheduling problem

Setting

• We are given set of $n$ requests $R=\{\mathrm{Req}(1),\mathrm{Req}(2),\cdots ,\mathrm{Req}(i),\cdots ,\mathrm{Req}(n)\}$
• $\{\mathrm{Req}(i)\}$ has a start time by $\mathrm{Start}(i)$ and a finish time given by $\mathrm{Finish}(i)$
• Additionally, each $\mathrm{Req}(i)$ has a weight/value given by $\mathrm{Weight}(i)$
• There is a machine which can handle one request at a time
• Two requests “conflict” if they overlap

The

Select a set $C\subseteq R$ of requests such that ${\sum }_{i\in C}\mathrm{Weight}(i)$ is maximised and no two requests from $C$ conflict.

Correct algorithm via dynamic programming

Order the requests in increasing order of finish times.

$$\mathrm{Finish}(1)<\mathrm{Finish}(2)<\cdots <\mathrm{Finish}(n-1)<\mathrm{Finish}(n)\to O(n\cdot \log n)$$

For each request $j$, we define $\mathrm{Last}(j)$ to be last compatible request with $j$

$$\mathrm{Last}(j)=\{\begin{array}{l}i\text{the largest index }i\text{ such that }i\text{ is disjoint from }j\\ 0\text{if there is no request }i<j\text{ is disjoint from }j\end{array}$$

There are $n$ requests $1,2,\cdots ,n$ ordered in increasing order of finish times. We will maintain an array $M$ of length $n$: for each $1\le j\le n$

• $M[j]$ stores the value of the set of requests of maximum weight which can be chosen for the sub-instance containing requests $\{1,2,\cdots ,j\}$

Goal: Compute $M[j]$ from the entries $M[1],M[2],\cdots ,M[j-1]$

• $\cdots$ which we have computed previously
• Bottom-up approach

Easy, but crucial, observation while computing $M[j]$ Either the request $j$ is chosen in $M[j]$ or not

• If request $j$ is chosen, then we should set $M[j]=\mathrm{Weight}(j)+M[\mathrm{Last}(j)]$
  • Follows fm definition of $\mathrm{Last}(j)$ and the array $M$
• If request. $j$ is not chosen, then we should set $M[j]=M[j-1]$
  • Follows from definition of the array $M$.

Recurrence: $M[j]=\max \{\mathrm{Weight}(j)+M[\mathrm{Last}(j)];M[j-1]\}$

Algorithm : Weighted Interval Scheduling with $n$ requests $\{1,2,\cdots ,n\}$

$$\begin{array}{rl}1:& M[0]=0\\ 2:& \text{for }j=1,2,\cdots ,n\text{ do}\\ 3:& M[j]=\max \{\mathrm{Weight}(j)+M[\mathrm{Last}(j)],M[j-1]\}\\ 4:& \text{end for}\end{array}$$

Correctness

• Proof by induction on $j$
• Base case is $j=0$
• Inductive step essentially argues the correctness of the recurrence

Running time

• Sort the requests in increasing order of finish times in $O(n\log n)$ time
• This allows us to find $\mathrm{Last}(j)$ for each $1\le j\le n$
• Filling up the entry for $M[j]$ needs to look at two existing entries from the array $M$, and do one addition & one max operation
  • This needs constant time
• Hence, time required to fill up all entries is $O(n)$

Note

The running time of DP algorithms is measured in terms of size of the array/table and amount of operations needed to compute this array/table.