Greedy algorithm A selects a time instance when the maximum number of celebritie

Question

Greedy algorithm A selects a time instance when the maximum number of celebrities are present simultaneously. An ad is scheduled at this time and the celebrities covered by this ad are then removed from further consideration. The algorithm A is then applied recursively to the remaining celebrities. Give an example where this algorithm shows more ads than is necessary.

I am having trouble fnding a solution for this specific dataset, since it seems intuitive to me that the algorithm would first pick a time, between 5 and 50, and then between 120 and 150, thus finding an optimal solution. I have found solutions with example datasets, whose solutions i understand, i am simply struggling with this particular set of data.

I. (35 pts) An exhibition is going on in a town today from t = 0 (9 am) to t = 720 (6 pm), and celebrities will attend!! There are n celebrities Ci,..., Cn and each celebrity Ci will attend during a time interval , : [G, uj] where in 0 lj

Explanation / Answer

This data set will always produce optimum results with the greedy algorithm approach. The question says to workout other data sets which provide non-optimum results(i.e. showing more ads than necessary) using the given approach.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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