Pythonで倉庫（godown）に入れられる箱の数を求めるプログラム

2つの整数型の配列があるとします。片方のリストには単位幅の箱の高さが、もう片方の配列には倉庫（godown）内の各部屋の高さが格納されています。部屋には0からnまでの番号が付いており、それぞれの高さは配列godownの対応するインデックスで与えられます。ここで、倉庫に押し込むことのできる箱の数を求めます。ただし、以下の条件に注意が必要です。

• 箱を積み重ねることはできません。
• 箱の並び順は自由に入れ替えて構いません。

箱は倉庫の左側または右側のどちらからでも挿入できます。ある箱が部屋の高さより高い場合、その箱と、それより右側にあるすべての箱は倉庫に入れることができません。

たとえば、入力がboxes = [4, 5, 6]、godown = [4, 5, 6, 7]の場合、出力は3になります。与えられた3つの箱は、すべて倉庫に収めることができます。

解き方の手順

この問題は、次の手順で解くことができます。

1. リストboxesを降順にソートする
2. l := 0 とする
3. r := godownのサイズ − 1 とする
4. bi := 0、ret := 0 とする
5. bi < boxesのサイズ かつ l <= r の間、以下を繰り返す
   • godown[l] > godown[r] の場合：boxes[bi] <= godown[l] ならば、ret を1増やして l を1進める
   • それ以外の場合：boxes[bi] <= godown[r] ならば、ret を1増やして r を1減らす
   • bi を1増やす
6. ret の値を返す

考え方のポイント

箱を高い順に処理することで、「大きな箱ほど置ける場所が限られる」という性質を活かしています。残っている部屋の左端と右端のうち、天井が高い側から貪欲に箱を収めていくことで、できるだけ多くの箱を詰め込めます。両端を指すポインタlとrが交差すると、それ以上箱を入れられる部屋はなくなります。

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