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) ).

—-

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: