Interval scheduling with weights. Consider the interval scheduling problem discussed in class. In that problem, we wanted to scheduling as many non-overlapping jobs as possible, and we saw that a greedy algorithm based on the earliest finish time first strategy worked.

Now suppose that each job j has a non-negative weight wj , and the goal is to schedule a set A of nonoverlapping jobs such that the sum of weights P jA wj is maximized.

(a) Show that the greedy algorithm based on earliest finish time first does not work in this setting. You should give a counter-example for which the greedy algorithm fails to find the best solution.

(b) Show how to efficiently solve this problem using Dynamic Programming. As in Problem 2, first design a recursive algorithm, identify the subproblems, and then memoize.

7. Interval scheduling with weights. Consider the interval scheduling problem discussed in class. In that problem, we wanted to scheduling as many non-overlapping jobs as possible, and we saw that a greedy algorithm based on the "earliest finish time first" strategy worked. Now suppose that each job j has a non-negative weight w,, and the goal is to schedule a set A of non- overlapping jobs such that the sum of weights ; is maximized. (a) Show that the greedy algorithm based on "earliest finish time first" does not work in this setting. You should give a counter-example for which the greedy algorithm fails to find the best solution. (b) Show how to efficiently solve this problem using Dynamic Programming. As in Problem 2, first design a recursive algorithm, identify the subproblems, and then memoize. 7. Interval scheduling with weights. Consider the interval scheduling problem discussed in class. In that problem, we wanted to scheduling as many non-overlapping jobs as possible, and we saw that a greedy algorithm based on the "earliest finish time first" strategy worked. Now suppose that each job j has a non-negative weight w,, and the goal is to schedule a set A of non- overlapping jobs such that the sum of weights ; is maximized. (a) Show that the greedy algorithm based on "earliest finish time first" does not work in this setting. You should give a counter-example for which the greedy algorithm fails to find the best solution. (b) Show how to efficiently solve this problem using Dynamic Programming. As in Problem 2, first design a recursive algorithm, identify the subproblems, and then memoize