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 '