Pythonで複数の区間の共通部分（交差する間隔）を見つける方法

この記事では、Pythonを使って複数の区間（インターバル）の共通部分を見つけるアルゴリズムを解説します。

問題の概要

各要素が [start, end] の形式で表される区間のリストが与えられます。ここで start は区間の開始時刻、end は終了時刻を意味し、両端を含むものとします。このとき、与えられたすべての区間に共通して含まれる区間（交差部分）を求めるのが目的です。

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

[[10, 110], [20, 60], [25, 75]]

この場合、3つの区間すべてに共通する範囲は [25, 60] となります。なぜなら、最も遅い開始時刻が 25、最も早い終了時刻が 60 だからです。

解法のアプローチ

この問題は非常にシンプルな発想で解くことができます。ポイントは以下の2点です。

• 共通区間の開始位置 ＝ 各区間の開始位置のうち最大のもの
• 共通区間の終了位置 ＝ 各区間の終了位置のうち最小のもの

具体的には、次の手順で処理を進めます。

1. リストから1つの区間を取り出し、初期値として start と end に設定します。
2. リストが空になるまで、残りの区間を1つずつ取り出しながら以下を繰り返します。
   • start = max(start, start_temp) … 開始位置は大きい方を採用
   • end = min(end, end_temp) … 終了位置は小さい方を採用
3. 最終的に得られた [start, end] を結果として返します。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, intervals):
        start, end = intervals.pop()
        while intervals:
            start_temp, end_temp = intervals.pop()
            start = max(start, start_temp)
            end = min(end, end_temp)
        return [start, end]

ob = Solution()
intervals = [[10, 110], [20, 60], [25, 75]]
print(ob.solve(intervals))

入力

[[10, 110], [20, 60], [25, 75]]

出力

[25, 60]

計算量について

このアルゴリズムは、各区間を一度ずつ処理するため、時間計算量は O(n)（n は区間の数）、空間計算量は O(1) となります。追加のデータ構造が必要ないため、非常に効率的な解法と言えます。

まとめ

複数の区間の共通部分を求める問題は、「開始位置の最大値」と「終了位置の最小値」を求めるだけで解決できます。max() と min() を活用したシンプルな実装で、線形時間で処理できる点が魅力です。スケジュール管理や時間帯の重なり判定など、実務でも応用範囲の広いテクニックなので、ぜひ覚えておきましょう。