Pythonで別の箱の中に収められる箱の最大数を求めるプログラム

問題の概要

複数の箱(ボックス)のリストがあり、各行はそれぞれの箱の幅と高さを表しているとします。ある箱は、幅と高さがどちらも相手の箱より小さい場合に限り、別の箱の中に収めることができます。この条件のもとで、1つの箱の中に最大で何個の箱を入れ子にできるかを求めるのがこの問題です。

例として、次の入力を見てみましょう。

この場合の出力は 3 になります。[6, 6] の箱を [10, 10] の箱の中に収め、さらにそれを [12, 12] の箱の中に収めることができるためです。なお [5, 10] の箱は、幅は [10, 10] より小さいものの高さが等しいため、入れ子にすることができません。

解決のためのアプローチ

この問題は、最長増加部分列(LIS)の考え方を応用し、二分探索を組み合わせることで O(n log n) の計算量で効率的に解くことができます。手順は以下の通りです。

• 関数 insert_index() を定義します。引数として配列 arr と高さ this_h を受け取ります。
• l := 0
• r := 配列 arr のサイズ − 1
• res := 0
• l <= r の間、以下を繰り返します。
  • m := l + (r − l) // 2
  • cur_h := arr[m]
  • cur_h < this_h が成り立つ場合:
    • res := m
    • l := m + 1
  • それ以外の場合:
    • r := m − 1
• res + 1 を返します。

メインの処理では、以下を実行します。

• 箱のリスト(マトリクス)を幅の昇順でソートします。幅が同じ場合は高さの降順でソートします。
• n := マトリクス内の要素数
• heights := サイズ (n + 1) のリストを作成し、すべて正の無限大(inf)で初期化します。
• heights[0] := 負の無限大(-inf)
• res := 0
• マトリクス内の各 box に対して、以下を繰り返します。
  • [cur_w, cur_h] := box
  • index := insert_index(heights, cur_h)
  • heights[index] >= cur_h の場合:
    • heights[index] := cur_h
  • res := res と index の最大値
• res を返します。

幅が同じ箱同士を互いに入れ子にしないようにするため、同じ幅の場合は高さを降順に並べて処理する点がポイントです。

実装例

理解を深めるために、実際のコードを見てみましょう。

class Solution:
    def solve(self, matrix):
        matrix = sorted(matrix, key=lambda x: (x[0], -x[1]))
        n = len(matrix)

        heights = [float("inf")] * (n + 1)
        heights[0] = float("-inf")
        res = 0

        for box in matrix:
            cur_w, cur_h = box
            index = self.insert_index(heights, cur_h)

            if heights[index] >= cur_h:
                heights[index] = cur_h
            res = max(res, index)
        return res

    def insert_index(self, arr, this_h):
        l = 0
        r = len(arr) - 1
        res = 0
        while l <= r:
            m = l + (r - l) // 2
            cur_h = arr[m]
            if cur_h < this_h:
                res = m
                l = m + 1
            else:
                r = m - 1
        return res + 1

ob = Solution()
matrix = [
    [12, 12],
    [10, 10],
    [6, 6],
    [5, 10]
]
print(ob.solve(matrix))

入力

matrix = [
[12, 12],
[10, 10],
[6, 6],
[5, 10] ]

出力

3

このように、二分探索による挿入位置の特定とLIS風の更新処理を組み合わせることで、与えられた箱の中に最大で何個の箱を入れ子にできるかを効率的に求めることができます。