Dock of the Bay You are in charge of the port of Oakland, where n ships are pres

Question

Dock of the Bay

You are in charge of the port of Oakland, where n ships are present. Ship i holds ci containers and must depart the port by time ti . Unloading a ship takes one hour, independently of how many containers are on it. Only a single ship may be unloaded at any given moment. The unloading of any ship can start as early as time 0. Develop a greedy algorithm to select which ships to unload so as to maximize the total number of containers unloaded. Hint: make one safe decision after another

Explanation / Answer

Solution:

Algorithm:

Correctness: The above algorithm will work fine since the containers which are being unloaded are unloaded with in order of their highest capacity and which is a greedy approach and one condition is made sure that the container's departure time must come after it is unloaded, only in that case the container is selected to unload.

Running time: 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 D
• Subjects

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