Pythonでgodownに入れるボックスの数を見つけるためのプログラム

整数を含む2つの配列があるとします。 1つのリストには、いくつかのユニット幅ボックスの高さが含まれ、別の配列には、godownの部屋の高さが含まれます。部屋には0...nの番号が付けられ、部屋の高さは配列godownのそれぞれのインデックスに示されます。ゴダウンに押し込める箱の数を調べなければなりません。いくつかの点に注意する必要があります

• ボックスを重ねることはできません。

• ボックスの順序は変更できます。

• ボックスは左から右にのみゴダウンに入れられます。

ボックスが部屋の高さよりも高い場合、そのボックスとその右側のすべてのボックスをゴダウンに押し込むことはできません。

したがって、入力がboxes =[4,5,6]、godown =[4、5、6、7]の場合、出力は1になります。挿入できるボックスは1つだけです。最初の部屋のサイズは4で、ボックスを最初の部屋に押し込む必要があり、その長さが他のボックスよりも短いため、残りの部屋をゴダウンに押し込むことはできません。

これを解決するには、次の手順に従います-

• リストボックスを並べ替える

• curmin：=godownの最初の要素を含む新しいリスト

• cm：=curmin [0]

• 範囲1からgodownのサイズのiの場合、実行します

  • cur：=godown [i]

  • cur

    • cm：=cur

  • curminの最後にcmを挿入します

• i：=0

• j：=倉庫のサイズ-1

• r：=0

• j> =0およびi<ボックスのサイズ、do

  • curmin [j]> =box [i]の場合、

    • i：=i + 1

    • r：=r + 1

  • j：=j-1

• rを返す

例（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