Hello. I\'m looking for help with this practice question for an exam review. I j

Question

Hello.

I'm looking for help with this practice question for an exam review.
I just need Pseudo-code of this please.

I want to make sure I understand the idea of how to do this well enough.

Thanks a lot

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 -1,3], 122,4], and Is-3.5,4.5 and suppose that w(h)-W(1s) = 1 and to(12)-10. Then, the optinal solution to this problem would be {/2) and not {/, Is) because the weight of 12 is 10 whereas the weight of , 12 is 1- 2 (a) The greedy algorithm that we used to solve the Interval Scheduling problem repeatedly picked an interval with carlicst 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.

Explanation / Answer

Solution (a): The given example itself is not solved with the given algorithm. That is sorting the intervals based on finish time. So we have interval I1 =[1,3], I2 =[2,4] and I3 = [3.5,4.5] which when sorted with finish times we get the Interval sequence as I1 I2 I3 . So the given algorith will pick I1 and I3 whose cost will be 2 but we have I2 which costs 10. thus the given algorithm is not solving the weighted interval problem.

Solution(b): The algorithm given will not be able to solve the weighted interval problem.

Consider the following example intervals and their weights

I1 = [1,5] w(I1) = 90

I2 = [2.5, 7.5]   w(I2) = 100

I3 = [5.5, 9.5]   w(I3) = 80

Now according to the algorithm we need to choose the interval with heaviest weight. So we pick I2 as its weight is 100. We cannot pick I1 or I3 as they both overlap with interval I2. So according to the algorithm we get the solution as maximum weight as 100. But the optimal solution is {I1,I3} as they both are non overlapping and their total weight is 180 which is greater than 100. Thus we are not getting the optimal solution if we greedily select the heaviest interval. Hence the given algorithm is not the correct one to find the maximum weight of non overlapping intervals.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.