Pythonでターゲット区間をマージして最終的な区間リストを求める方法

この記事では、重なり合わない（非オーバーラップの）区間リストに対して、新しいターゲット区間を挿入・マージし、結果として得られる区間リストも依然として重複がなくソート済みである状態を保つアルゴリズムを、Pythonで実装する方法を解説します。

問題の概要

前提条件として、与えられる区間のリストは以下の性質を持ちます。

• 各区間は互いに重なっていない（non-overlapping）
• 終了時刻に基づいてソートされている

ここに新たな区間 target が与えられたとき、target を既存の区間と適切にマージし、最終的な区間リストを求めます。マージ後もリストは「重複なし・ソート済み」の状態を維持しなければなりません。

例：

入力が次のような場合を考えます。

intervals = [[1, 15], [25, 35], [75, 90]]
target = [10, 30]

このとき出力は以下のようになります。

[[1, 35], [75, 90]]

これは、target の [10, 30] を挿入すると、既存の区間 [1, 15] と [25, 35] の両方と重なるため、これら3つが1つの区間 [1, 35] に統合されるからです。[75, 90] はどの区間とも重ならないためそのまま残ります。

解法のアプローチ

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

1. target を区間リスト iv の末尾に追加します。
2. iv を開始時刻（start time）に基づいてソートします。
3. 結果リスト res を作成し、最初の区間を格納します。
4. インデックス i を 1 として初期化します。
5. i が iv のサイズ未満である限り、以下を繰り返します。
   • iv[i] の開始時刻が、res の最後の区間の終了時刻以下であれば、両区間は重なっているためマージします。具体的には、res の最後の区間の終了時刻を「現在の終了時刻」と「iv[i] の終了時刻」の最大値に更新します。
   • そうでなければ（重なっていなければ）、iv[i] を res の末尾に追加します。
6. i を 1 ずつ増やします。
7. ループ終了後、res を返します。

このアルゴリズムの計算量は、ソート部分が O(n log n)、マージ処理が O(n) となるため、全体として O(n log n) です。

Pythonでの実装例

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

class Solution:
    def solve(self, iv, target):
        # ターゲット区間をリストに追加
        iv.append(target)
        # 開始時刻を基準にソート
        iv.sort(key=lambda x: x[0])
        # 結果リストを最初の区間で初期化
        res = [iv[0]]
        i = 1
        while i < len(iv):
            if iv[i][0] <= res[-1][1]:
                # 重なっている場合は終了時刻を拡張してマージ
                res[-1][1] = max(res[-1][1], iv[i][1])
            else:
                # 重なっていない場合は新しい区間として追加
                res.append(iv[i])
            i += 1
        return res

ob = Solution()
intervals = [
    [1, 15],
    [25, 35],
    [75, 90]
]
target = [10, 30]
print(ob.solve(intervals, target))

入力

[[1, 15], [25, 35], [75, 90]], [10, 30]

出力

[[1, 35], [75, 90]]

コードのポイント

• ソートの重要性： target を追加した後に開始時刻でソートすることで、隣接する区間同士だけを比較すればよくなり、処理がシンプルになります。
• max() によるマージ： 区間が完全に内包されるケース（例：[10, 30] が [5, 40] に含まれる場合）でも正しく動作するよう、終了時刻は max() で更新します。
• 破壊的変更に注意： この実装では引数のリスト iv を直接変更（append・sort）しています。元のリストを保持したい場合は、事前にコピーを作成してください。

この手法は、カレンダーの予定管理やスケジュールの空き時間計算など、実際のアプリケーションでも広く応用される基本的なアルゴリズムです。