Algorithims. Greedy Algorithims

2. A variant of the Interval Scheduling problem is one in which each interval has an associated non-negative weight. In this problem (called the Weighted Interval Scheduling problem), we want to find a set of mutually non-overlapping intervals that have the maximum total weight. For example, consider intervals 11 = [1,3], 12 = [2,41, and 13 = [3.5, 4.5 and suppose that w(11) = w(s) = 1 and w(12) 10. Then, the optimal solution to this problem would be {I2] and not {1, Is because the weight of I2 is 10 whereas the weight of 11, 12) is 1 1-2. (a) The greedy algorithm that we used to solve the Interval Scheduling problem repeatedly picked an interval with earliest finish time and deleted other intervals that overlapped the selected interval. Show that this algorithm does not produce an optimal solution to the Weighted Interval Scheduling problem (b) What about an algorithm that repeatedly picks a heaviest interval from all that are available and then deletes other intervals that overlap with the chosen interval? Does this algorithm always produce an optimal solution? If yes, then prove correctness of the algorithm and if no, then construct a counter-example