Given n open intervals (a1, b1), (a2, b2), . . . , (an, bn) on the real line, ea

Question

Given n open intervals (a1, b1), (a2, b2), . . . , (an, bn) on the real line, each representing start and end times of some activity requiring the same resource, the task is to find the largest number of these intervals so that no two of them overlap. Investigate the three greedy algorithms based on a. earliest start first. b. shortest duration first. c. earliest finish first. For each of the three algorithms, either prove that the algorithm always yields an optimal solution or give a counterexample showing this not to be the case.

Explanation / Answer

Earliest Start Time, Shortest Duration will not give optimal solutins. EXAMPLE-(1,100), (2,3), (4,5)---Earliest Time will Fail. EXAMPLE-(1,4),(5,9),(3,6)----Shortest Duration Will Fail. Earliest End Time Will always give optimal soution Proof: Consider an Optimal Solution O and a Greedy solution by earliest end first G. Now, Let the total duration for the event be T. Assume that for time t(

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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