# Dynamic Programming – 1 : Weighted Interval Scheduling

In general, problems on dynamic programming can be solved by first expressing the required optimum solution in a recursive fashion, and then solving the recurrence in a bottom-up fashion.

Weighted Interval Scheduling

We are given $n$ intervals, with each interval having start time $S_i$, finish time $F_i$ and non-negative weight $W_i$ ( for $i$ from 1 to $n$).

Our task is to find a compatible subset $T$  of these intervals so as to maximize $\sum W_I$ for the intervals in $T$.

(A compatible subset is one where no two intervals ever overlap. )

—-

Solution.

Let us assume that the $n$ intervals are sorted in the order of their finish times. Let this ordered list of intervals be $I_1, \ldots, I_n$.

Let OPT (n) denote the value of optimum solution. (i.e. the sum of weights of intervals in an optimum solution.)

Consider interval $I_n$.

The optimum solution may either include $I_n$ or not include $I_n$.

If the optimum solution does not include $I_n$, then we have:

$OPT (n) = OPT (n-1)$.

Notation: Here, $OPT ( k )$ denotes the optimum value computed from the set of intervals $\{I_1, \ldots, I_k\}$.

If the optimum solution does includes $I_n$, then, apart from $I_n$, the optimum solution can only include those intervals which do not overlap with it, i.e. only those intervals, $i$ for which $F_i \leq S_n$.

Notation Let $p ( k )$ denote the index of the interval, $i$ for which (1) $F_i \leq S_k$, and (2) $F_{i+1} > S_k$. Also, if all intervals have finish times $> S_k$, then $p_k = 0$.

Thus, we have that, if the optimum solution includes $I_n$, then:

$OPT (n) = W_n + OPT (p(n))$.

Therefore,

$OPT (n) = max \{ OPT (n-1), W_n + OPT (p(n)) \}$

Generalizing, we have that, for $1 \leq i \leq n$ :

$OPT ( i ) = max \{ OPT (i-1), W_i + OPT (p(i)) \}$

and that, $OPT (0) = 0$.

—–

Using the above recurrence, we can write an algorithm to solve it in a bottom-up fashion:

/* Assuming that intervals are sorted according to $F_i$ values we have $p_i$ values for all intervals. */

OPT (0) = 0;

For i from 1 to n:

Compute OPT(i) using the above recurrence.

Return OPT (n).
End.

—–

The above algorithm takes O(n) time.

Sorting the intervals by $F_i$ values takes $O(n \log n)$ (using merge sort or quick sort), following which we can compute $p_i$ values for all intervals in $O(n \log n)$ time (by calling a slightly modified binary search routine $n$ times).

Therefore, the algorithm will run in $O(n \log n)$ time.

——

Computing the optimal solution from the optimal value:

Once we have the OPT values, we can compute the optimal solution (i.e. the sets of intervals, not just the value) recursively as follows:

Function: OPT_Solution ( k ) :=

If ( k == 0 )

//Do nothing. Break recursion.

Return;

For i decreasing from k to 1:

If [ OPT ( p(k) ) + W_k >= OPT (k-1) ]

OPT_Solution ( p(k) );

// Include interval k in Optimum solution

Print k.

Else

OPT_Solution (k-1);

End of function.

—-

The function OPT_Solution (n) has a worst-case running time of O(n) [because there can be at most n recursive calls (since the argument passed to the function calls strictly decreases), and the time taken to process the non-recursive part of each call is O(1) ).

—-