用Python找出要放入货仓的盒子数量的程序

假设,我们有两个包含整数的数组。一个列表包含一些单位宽度框的高度,另一个数组包含仓库中房间的高度。房间编号为 0...n,房间的高度在数组 godown 中各自的索引中提供。我们必须找出可以推入仓库的箱子数量。有几件事必须牢记,

  • 箱子不能叠在一起。

  • 可以更改框的顺序。

  • 箱子只从左到右放入仓库。

如果一个盒子比房间的高度高,那么这个盒子和它右边的所有盒子都不能被推入仓库。

所以,如果输入像boxes = [4,5,6], godown = [4, 5, 6, 7],那么输出就会是1 只能插入一个box。第一个房间是4号房间,其余的不能推入货仓,因为箱子必须推过第一个房间,而且它的长度比其他箱子小。

示例(Python)

让我们看看以下实现以获得更好的理解 -

def solve(boxes, godown):
   boxes.sort()
   curmin = [godown[0]]
   cm = curmin[0]
   for i in range(1, len(godown)):
      cur = godown[i]
      if cur < cm:
         cm = cur
      curmin.append(cm)
   i,j = 0, len(godown)-1
   r = 0
   while j >= 0 and i < len(boxes):
      if curmin[j] >= boxes[i]:
         i += 1
         r += 1
      j -= 1
   return r

print(solve([4,5,6], [4, 5, 6, 7]))

输入

[4,5,6], [4, 5, 6, 7]
输出结果
1