Pythonで重なる区間をマージし、最長の区間の長さを求めるプログラム

問題の概要

それぞれ [start, end] の形式で表される区間（インターバル）のリストが与えられているとします。この課題では、重なり合う区間をいくつでもマージ（統合）して作ることができる「最も長い区間」の長さを求めます。

例えば、入力が [[1, 6], [4, 9], [5, 6], [11, 14], [16, 20]] の場合を考えてみましょう。[1, 6]、[4, 9]、[5, 6] は互いに重なっているため、これらをマージすると長さ9の区間 [1, 9] が得られます。したがって、出力は 9 となります。

解法のアルゴリズム

この問題は、以下の手順で効率よく解くことができます。

1. 区間のリストをソートします。
2. union を、リストの最初の区間で初期化します。
3. best を union[終了] - union[開始] + 1 で初期化します。
4. 2番目以降の各区間について、開始時刻 s と終了時刻 e を順に処理します。
   • s が union[終了] 以下の場合（現在の統合区間と重なっている場合）：union[終了] を union[終了] と e のうち大きい方に更新します。
   • それ以外の場合（重なっていない場合）：新しい区間 [s, e] を union として設定します。
   • best を、現在の best と union[終了] - union[開始] + 1 のうち大きい方に更新します。
5. best を返します。

このアプローチのポイントは、あらかじめ区間をソートしておくことで、隣接する区間同士を一度の走査で比較・統合できる点にあります。計算量はソートが支配的となるため、O(n log n) で処理できます。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
    def solve(self, intervals):
        intervals.sort()
        union = intervals[0]
        best = union[1] - union[0] + 1
        for s, e in intervals[1:]:
            if s <= union[1]:
                union[1] = max(union[1], e)
            else:
                union = [s, e]
                best = max(best, union[1] - union[0] + 1)
        return best
ob = Solution()
intervals = [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]
print(ob.solve(intervals))

入力

[[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]

出力

9

まとめ

このプログラムでは、区間をソートした上で先頭から順に走査し、重なる区間を統合しながら最長の区間の長さを追跡しています。サンプル入力では [1, 6]、[4, 9]、[5, 6] が統合されて長さ9の区間となるため、正しく 9 が出力されます。区間のマージ処理はスケジューリングやデータ集約など、さまざまな場面で応用できる基本的なテクニックです。