suppose we have some 2D boxes in a container surrounded by water. Unfortunately there is a hole in left hand side wall of container. The height of this hole is more than height of all boxes.length of all boxes is 1 m and their height is an integer.all boxes are put in one line.in every second the amount of water which insert through container is one square meter(take care our problem is in 2D context).we want to find how long it takes till a given box is one meter under the water.
is there any greedy algorithm to efficiently solve this?
what is the greedy approach of this?
279 Views Asked by user3070752 At
1
I think this algorithm can solve this in O(n).
from the i-th box we first go to the end of line to find the first box which is a higher than the i-th box.since differences between all boxes' height is at least 1 meter so water can't go further than this box.then we go from the i-th box to the beginning of the line.we save height of the i-th box in Max_Height variable.each time we find a box higher than this Max_Height we update Max-Height.so whenever we find a box shorter than the Max_Height we add (Max_Height - box's height) to our result.at the end we have computed area of all previous and next wells.so we just need to compute the distance between the first next higher box and the first previous higher box and add it to our result. That's it.