In a galaxy far, far away, the Empire has built n Death Satellites to attack n p

Question

In a galaxy far, far away, the Empire has built n 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. The i-th satellite has power fi , while the shield on planet j can tolerate up to sj power. A successful attack on the i-th planet brings benefit bi to the Empire. That is, if planet i is attacked by the j-th satellite and fj > 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 log n) time, using a greedy algorithm.

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 I
• Subjects

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