Dynamic Programming – 1 : Weighted Interval Scheduling
February 3, 2011 Leave a comment
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 intervals, with each interval having start time , finish time and non-negative weight ( for from 1 to ).
Our task is to find a compatible subset of these intervals so as to maximize for the intervals in .
(A compatible subset is one where no two intervals ever overlap. )
Let us assume that the intervals are sorted in the order of their finish times. Let this ordered list of intervals be .
Let OPT (n) denote the value of optimum solution. (i.e. the sum of weights of intervals in an optimum solution.)
Consider interval .
The optimum solution may either include or not include .
If the optimum solution does not include , then we have:
Notation: Here, denotes the optimum value computed from the set of intervals .
If the optimum solution does includes , then, apart from , the optimum solution can only include those intervals which do not overlap with it, i.e. only those intervals, for which .
Notation Let denote the index of the interval, for which (1) , and (2) . Also, if all intervals have finish times , then .
Thus, we have that, if the optimum solution includes , then:
Generalizing, we have that, for :
and that, .
Using the above recurrence, we can write an algorithm to solve it in a bottom-up fashion:
/* Assuming that intervals are sorted according to values we have values for all intervals. */
OPT (0) = 0;
For i from 1 to n:
Compute OPT(i) using the above recurrence.
Return OPT (n).
The above algorithm takes O(n) time.
Sorting the intervals by values takes (using merge sort or quick sort), following which we can compute values for all intervals in time (by calling a slightly modified binary search routine times).
Therefore, the algorithm will run in 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.
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
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) ).