Chapter 6: Dynamic Programming

In previous chapters, we discovered that we can use a greedy approach to this problem to find an optimal solution to the generic Interval Scheduling Problem. We will now look at the Weighted Interval Scheduling Problem, where each interval is assigned a particular value or weight, and we are looking to maximize the total value scheduled. The original Interval Scheduling Problem addresses a special case where all weights of the intervals are equal to 1, but can't be applied to the situation where the weights are different. Using a greedy approach to this problem will not produce an optimal solution, which is why we will use dynamic programming to solve the problem. We will use a recursive algorithm to solve the problem initially. The same properties of the initial Interval Scheduling Problem remain the same in the Weighted version. We have a set of n intervals 1,2,…,n that each have a start time, and a finish time. However, now each interval also has a weight associated with it. Two intervals are considered compatible if their times do not overlap. The goal of the problem is to maximize the overall total value by selecting a set of intervals that are mutually compatible. To start, we will sort the intervals by decreasing finish time. An interval i comes before an interval j if i<j. We will then define p(j) for an interval j, to be the largest index i<j such that i and j are compatible. P(j) = 0 if there is no interval i<j that is compatible with j. We then look at a very obvious observation about our optimal schedule. For each job, the optimal solution will either include it, or not include it. If we choose to include job n, then that means no job between n and p(n) is included in the optimal solution, because there would be overlap. Thus, the optimal solution must also include the optimal solution to the problem of 1,2,…,p(n) intervals. If a job is not included in the optimal solution, then the problem becomes reduced to the optimal solution of 1,2,…,n-1 intervals. Therefore, combining these two options, the optimal solution of a list of intervals of size j is OPT(j) = max(vj + OPT(p(j)), OPT(j-1). Thus, job j is included in the optimal solution IF AND ONLY IF vj+OPT(p(j)) >= OPT(j-1). This solution shows the basic components of dynamic programming: a recurrence equation that expresses the optimal solution in terms of the optimal solutions to smaller subproblems. Using this algorithm, the run time to solve the problem would be exponential, similar to that of the Fibonacci numbers. However, we can improve it using a technique known as 'Memoization'. To do this, we can store already computed values that we know we might need again so that instead of having to recompute them again, we only need to compute them once and then can access them in constant time from storage. For our algorithm, we will maintain and array M[0…n], where M[j] will start with the value of 'empty', but will hold the value of Compute-Opt(j) as soon as we have computed it. Using this implementation, the running time of the M-Compute-Opt(j) is O(n). At this point, we have only computed the value of the optimal solution, not returned the jobs included in the optimal solution. To achieve this, we will look at the values saved in the memoized array to determine which intervals were included to create the optimal solution. We know that an interval j belongs to the optimal solution if and only if vj+OPT(p(j)) >= OPT(j-1). Using this, we can trace back through the array of values to find which intervals are in the optimal solution. We check this comparison starting at the nth job, and then based on the result of whether n was or was not included, we either move to p(j) or n-1 respectively. Using this algorithm 'Find-Solution', we can return the optimal solution in O(n) time. This algorithm was easy to follow after having discussed it in class, I would give it a 9/10.