Google Phone Interview | India
Anonymous User
1154

You are trying to fit maximum number of objects into a storage area.

The storage area is a one-dimensional cave (with opening on one end), divided into equal-length segments of varying heights h_0, ..., h_n.

Objects are also of equal length and varying heights h_0, ..., h_k. Only one object can fit into one segment, and that is of course the height of the object is no larger than the height of the segment. Once the object is put in a segment, it renders inaccessible the rest of the storage space behind the blocked segment.

Objects are carried into the storage by means of a forklift, which means that if we want to put store it in a given segment, it must not only fit in that segment, but also in all previous segments (and of course no previous segment can be already occupied).

Storage space segment heights:
3, 4, 2, 3

Objects heights:
5, 1, 3, 3, 4

ans : 3

I tried sorting object heights, but failed in few cases.
can someone suggest solution to this problem?

Comments (8)