1. algorithm 2. proof of correctness. 1 Star Wars In a galaxy far, far away, the

Question

1. algorithm

2. proof of correctness.

1 Star Wars In a galaxy far, far away, the Empire has builtn Death Satellites to attack n planets controlled by the rebels (each satellite will attack exactly one planet). The Rebels have installed a defensive shield in each planet. Thei-th satellite has power fi, while the shield on planet j can tolerate up to si power. A successful attack on the i-th planet brings benefit b to the Empire. That is, if planet is attacked by the j-th satellite and fi > Si, then the Empire will receive benefit bi; otherwise, it will receive benefit 0. Match satellites to planets to maximize the Empire's benefit in O (n logn) time, using a greedy algorithm. Hint: Make one or more heaps.

Explanation / Answer

Solution:

Algorithm:

correctness: The arrays are sorted and only those values are being chosen as per greedy strategy whose value is sufficient to benefit the Empire.

Running time: Two times the sorting has been done in the given algorithm and one more for loop is there which is running n number of times.

so the effective time complexity will be

T(n)= O(n log n)

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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