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