6.1. Weighted Interval Scheduling: A Recursive Procedure

Chapter Six is concerned about ways of solving problems using Dynamic Programming techniques. When solving problems with Dynamic Programming, one implicitly explores the space of all possible solutions, by carefully decomposing them into several subproblems, and then building up correct solutions to larger and larger subproblems. With the Weighted interval scheduling problem, is a generalization of the Interval scheduling problem in which each interval has its own value(or weight), and our goal is to find a set of intervals of maximum value(or weight). It is different from the Interval scheduling problem we solved using greedy algorithms in that our goal for the Interval scheduling problem was to find a the biggest set of non-overlapping intervals which constituted our optimal solution. Here, we are concerned about the weight of the intervals, not matter how big our solution set is. Thus in many occasions, greedy algorithms don't work for the weighted interval scheduling.

The Setting

We have n requests labeled 1,…,n

Each request i has a start time s_i and a finish time f_i

Each interval i has a value(weight), v_i

Two intervals are compatible if they don't overlap

Our Goal is to select a subset S ⊆ {1,…,n} of mutually compatible intervals so as to maximize the sum of the values of the selected intervals, ∑_{i ∈ S} v_i

If we suppose that the requests are coming in order of non-decreasing finish time: f₁≤f₂,…,f_n,:

A request i comes before a request j if i<j.

We define p(j) for an interval j as the largest index i<j such that the intervals i and j are disjoint.

So i is the leftmost interval that ends before j begins.(We know we are considering jobs in a left to right order where the intervals are increasing from left to right.)

We define p(j) = 0 if no request i<j is disjoint from j.

Now let's consider an optimal solution O.

For the optimal solution O, we can say that: either interval n( the last one) belongs to O or it doesn't.

Let's explore both sides of the situation:

If n ∈ O, then no interval indexed between strictly between p(n) and n can belong to O because intervals p(n)+1, p(n) + 2,…,n-1 all overlap with n by definition.

In addition, if n ∈ O, then O must include an optimal solution to the problem consisting of requests {1,2,…,p(n)}: otherwise, we could replace O's choice of requests from {1,…,p(n)} with a better one, with no danger of overlapping request n.

If n ∉ O, then O is equal to the optimal solution to the problem consisting of requests {1,…,n-1}: we are assuming that O doesn't include n, thus if it doesn't choose the optimal set of requests from {1,…,n-1}, then we could replace if with a better one.

So in brief, finding the optimal solution on intervals :1,2,…,n} involves looking at the optimal solutions of smaller problems of the form {1,2,…,j}.

For any value of j in {1,2,…,n},let O_j denote the optimal solution to the problem consisting of requests {1,2,…,j}, and let OPT(j) denote the value of this solution.

OPT(0) =0, which is conventionally the optimum solution over an empty set of intervals.

Our goal is to find O_n with value OPT(n).

So, from what we have argued above, for the case j=n, either j ∈ O_j in which case OPT(j) = v_j + OPT(p(j)), or j∉ O_j in which case OPT(j) = OPT(j-1).

Thus from this, we can say that:

OPT(j) = max(v_j + OPT(p(j)),OPT(j-))

Request j belongs to the optimal solution on the set {1,2,…,j} if and only if v_j + OPT(p(j)) ≥ OPT(j-1).