Pythonでgodownに入れることができるボックスの数を調べるプログラム

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

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

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

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

したがって、入力がboxs =[4、5、6]、godown =[4、5、6、7]の場合、出力は3になります。入力として指定された3つのボックスすべてをgodownに入れることができます。

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

• リストボックスを降順で並べ替えます

• l：=0

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

• bi：=0

• ret：=0

• bi<ボックスのサイズとl<=r、do

  • godown [l]> godown [r]の場合、

    • box [bi] <=godown [l]の場合、

      • ret：=ret + 1

      • l：=l + 1

    • それ以外の場合

      • box [bi] <=godown [r]の場合、

        • ret：=ret + 1

        • r：=r-1

    • bi：=bi + 1

• retを返す

例（Python）

理解を深めるために、次の実装を見てみましょう-

def solve(boxes, godown):
   boxes.sort(reverse = True)

   l, r = 0, len(godown) - 1
   bi, ret = 0, 0
   while bi < len(boxes) and l <= r:
      if godown[l] > godown[r]:
         if boxes[bi] <= godown[l]:
            ret += 1
            l += 1
      else:
         if boxes[bi] <= godown[r]:
            ret += 1
            r -= 1
      bi += 1

   return ret

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

入力

[4, 5, 6], [4, 5, 6, 7]

出力

3