Pythonで2つの区間リストの重複部分を見つけて昇順に返す方法

閉区間（closed interval）からなる2つのリストがあるとします。それぞれのリストは単体では区間同士が重複しておらず、開始位置の昇順（非減少順）にソートされています。この記事では、2つのリストに共通して含まれる「重複する区間」をすべて見つけ出し、昇順に並べて返すPythonプログラムを解説します。

たとえば、入力が inv1 = [[50, 100],[190, 270],[310, 330]] と inv2 = [[40, 120],[180, 190]] の場合、出力は [[50, 100], [190, 190]] になります。

アルゴリズムの流れ

この問題は、マージ処理などでも使われる「2ポインタ」の考え方を応用すると、各リストを一度だけ走査するだけで解けます。手順は以下の通りです。

• 結果を格納するための空リスト ans を用意する
• ポインタ i と j をそれぞれ 0 で初期化する
• i が A の長さ未満 かつ j が B の長さ未満である間、次を繰り返す
  • start := max(A[i][0], B[j][0])、end := min(A[i][1], B[j][1]) を計算する
  • start <= end のとき、区間 [start, end] を ans に追加する
  • A[i][1] < B[j][1] なら i を1進め、そうでなければ j を1進める
• ans を返す

なぜこれでうまくいくのか

2つの区間の共通部分は、必ず「開始位置の大きい方」から「終了位置の小さい方」までの範囲になります。start <= end が成り立つときだけ実際の重なりが存在し、その区間が答えとなります。また、終了位置が早い側の区間から処理済みとしてポインタを進めることで、常に現時点で先頭にある2区間どうしを比較し続けられます。

実装上の重要なポイントは、重なりが検出されなかった場合でも必ずどちらかのポインタを進めることです。ポインタの更新を交差判定の中に入れてしまうと、重ならない区間に出会った時点で処理が止まり、無限ループに陥ってしまいます。

実装例

class Solution:
    def solve(self, A, B):
        ans = []
        i = 0
        j = 0
        while i < len(A) and j < len(B):
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            if start <= end:
                ans.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
        return ans

ob = Solution()
inv1 = [[50, 100],[190, 270],[310, 330]]
inv2 = [[40, 120],[180, 190]]
print(ob.solve(inv1, inv2))

入力

[[50, 100],[190, 270],[310, 330]], [[40, 120],[180, 190]]

出力

[[50, 100], [190, 190]]

計算量

時間計算量は O(n + m) です（n、m はそれぞれのリストに含まれる区間の数）。すべての区間ペアを総当たりで調べる O(n × m) のアプローチに比べ、はるかに効率的です。空間計算量については、出力用のリストを除けば O(1) で済みます。