Pythonで最長のボックスチェーンの長さを求めるアルゴリズムと実装方法

問題の概要

ここにボックス（箱）のリストがあるとします。各要素は [start, end] の2つの値を持ち、常に start < end が成り立ちます。あるボックスの「終点」と別のボックスの「始点」が一致する場合、それら2つのボックスをつなげることができます。このとき、形成できるボックスの連鎖（チェーン）のうち、最も長いものの長さを求めるのが目的です。

例として、入力が次のような場合を考えてみましょう。

blocks = [[4, 5], [5, 6], [4, 8], [1, 2], [2, 4]]

この場合、出力は 4 になります。これは以下のように4つのボックスで連鎖を作れるためです。

[1, 2] → [2, 4] → [4, 5] → [5, 6]

解法のアプローチ

この問題は動的計画法的な発想を使って効率的に解くことができます。手順は以下のとおりです。

• ボックスのリストが空の場合は 0 を返します。

• リスト boxes をソートします。

• 辞書（マップ）dic を用意します。dic[e] には「終点が e であるボックスで終わる最長チェーンの長さ」を記録します。

• 各ボックスの始点 s と終点 e に対して、次のように更新を行います。
  dic[e] = max(dic[e], dic[s] + 1)
  つまり、「s までのチェーンに続けて現在のボックスをつなげた場合」と「既に記録されている e でのチェーン長」を比較し、大きい方を採用します。

• 最後に、辞書内のすべての値の最大値を返せば、それが最長チェーンの長さです。

実装例

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

import collections

class Solution:
    def solve(self, boxes):
        if not boxes:
            return 0
        boxes.sort()
        dic = collections.defaultdict(int)
        for s, e in boxes:
            dic[e] = max(dic[e], dic[s] + 1)
        return max(dic.values())

ob = Solution()
boxes = [
    [4, 5],
    [5, 6],
    [4, 8],
    [1, 2],
    [2, 4]
]
print(ob.solve(boxes))

入力

[[4, 5],
[5, 6],
[4, 8],
[1, 2],
[2, 4]]

出力

4

処理の流れを詳しく解説

このコードがどのように動作するのか、ステップごとに確認してみましょう。

• まずリストをソートすると、[[1, 2], [2, 4], [4, 5], [4, 8], [5, 6]] となります。

• [1, 2] を処理：dic[2] = max(dic[2], dic[1] + 1) = 1

• [2, 4] を処理：dic[4] = max(dic[4], dic[2] + 1) = 2

• [4, 5] を処理：dic[5] = max(dic[5], dic[4] + 1) = 3

• [4, 8] を処理：dic[8] = max(dic[8], dic[4] + 1) = 3

• [5, 6] を処理：dic[6] = max(dic[6], dic[5] + 1) = 4

最終的に dic の値の最大値である 4 が答えとして返されます。なお、[4, 8] につながるチェーンは3で止まるため、最長チェーンには採用されません。

計算量について

ソートに O(n log n)、各ボックスの更新処理に O(n) かかるため、全体の計算量は O(n log n) です。ボックス同士を総当たりで比較する O(n²) のアプローチよりも高速に動作し、データ量が多い場合でも実用的なパフォーマンスを発揮します。