Nerd For Tech
Published in

Nerd For Tech

Photo by Elevate on Unsplash

Put Boxes Into the Warehouse I — Daily Challenge May

1564. Put Boxes Into the Warehouse I

  • Boxes cannot be stacked.
  • You can rearrange the insertion order of the boxes.
  • Boxes can only be pushed into the warehouse from left to right only.
  • If the height of some room in the warehouse is less than the height of a box, then that box and all other boxes behind it will be stopped before that room.

Example

Input: boxes = [4,3,4,1], warehouse = [5,3,3,4,1]
Output: 3
Explanation: We can first put the box of height 1 in room 4. Then we can put the box of height 3 in either of the 3 rooms 1, 2, or 3. Lastly, we can put one box of height 4 in room 0.
There is no way we can fit all 4 boxes in the warehouse.

Understanding the problem:

def maxBoxesInWarehouse(boxes, warehouse):
for i in range(1, len(warehouse)):
warehouse[i]= min(warehouse[i], warehouse[i-1])
boxes.sort(reverse=True)
j = 0
res = 0
for height in warehouse:
while j < len(boxes) and boxes[j] > height:
j += 1
if j >= len(boxes):
break
res += 1
j += 1
return res

Complexity Analysis:

  • Time complexity: O(n*log(n)) for sorting the boxes m for creating the min-height array. O(n + m) for finding the box for the room.
  • Constant space

--

--

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store