Pythonで倉庫（godown）に押し込めるボックスの数を求めるプログラム

問題の概要

2つの整数配列が与えられていると仮定しましょう。一方のリストには単位幅のボックスの高さが、もう一方の配列には倉庫（godown）内の各部屋の高さが格納されています。部屋には 0〜n の番号が付いており、各部屋の高さは godown 配列の対応するインデックスに記録されています。ここで、倉庫に押し込むことのできるボックスの数を求めます。

ただし、以下のルールを守る必要があります。

• ボックスを積み重ねることはできません。
• ボックスの順序は自由に入れ替えられます。
• ボックスは必ず左から右へ向かって挿入します。

もしボックスの高さがある部屋の高さより大きい場合、そのボックスおよびそれより右側のすべてのボックスは倉庫に入れることができません。

たとえば、boxes = [4,5,6]、godown = [4, 5, 6, 7] という入力の場合、出力は 1 になります。最初の部屋の高さが 4 しかないため、残りのボックスは最初の部屋を通過できず、倉庫の奥へ押し込むことができないからです。

解き方のアプローチ

この問題は「貪欲法」と「二ポインタ」を組み合わせることで効率的に解けます。ポイントとなる考え方は次のとおりです。

• 位置 j の部屋にボックスを届けるには、それより左側のすべての部屋の高さがボックス以上である必要があります。つまり、位置 j に置けるボックスの高さの上限は、godown[0..j] の最小値（接頭辞最小値）です。
• ボックスを小さい順にソートし、倉庫を右側から走査しながら、置ける部屋に小さいボックスから順に割り当てていきます。

具体的な手順は以下のとおりです。

1. リスト boxes をソートする。
2. curmin を、godown の最初の要素だけを含む新しいリストとして作成する。
3. cm := curmin[0] とする。
4. i を 1 から godown のサイズ未満まで繰り返す。
   • cur := godown[i]
   • cur < cm なら cm := cur と更新する。
   • cm を curmin の末尾に追加する。
5. i := 0、j := godown のサイズ − 1、r := 0 と初期化する。
6. j ≥ 0 かつ i < boxes のサイズである間、次を繰り返す。
   • curmin[j] ≥ boxes[i] なら、i := i + 1、r := r + 1 とする（ボックスを配置）。
   • j := j − 1 として、一つ左の部屋へ移動する。
7. 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

計算量

ボックスのソートに O(m log m)、接頭辞最小値の計算と二ポインタによる走査に O(n) かかるため、全体の時間計算量は O(m log m + n) です（m はボックスの数、n は部屋の数）。空間計算量は O(n) です。