Pythonで重なる区間をマージし、昇順に並べ替える方法

問題の概要

区間（インターバル）のリストが与えられたとき、それらを統合（マージ）し、ソート済みのシーケンスとして返すことを考えます。

例えば、入力が inv = [[2, 5], [4, 10], [20, 25]] の場合、[2, 5] と [4, 10] は重なっているため [2, 10] にまとめられ、出力は [[2, 10], [20, 25]] となります。

解決の手順

この問題は以下のステップで解くことができます。

• まず、区間のリストを開始位置を基準にソートします。これにより、マージ対象となる区間が必ず隣接するようになります。
• 結果を格納するための新しいリスト ans を用意します。
• ソート済みの各区間 (s, e) について次の処理を行います。
  • ans が空でなく、現在の区間の開始位置 s が ans の最後の区間の終了位置以下である場合（＝区間が重なっている場合）、最後の区間の終了位置を「現在の終了位置 e と既存の終了位置の最大値」で更新します。
  • それ以外の場合（＝区間が重なっていない場合）、新しい区間 [s, e] を ans に追加します。
• 最後に ans を返します。

このアルゴリズムの計算量は、ソート部分が O(n log n)、マージ処理が O(n) となり、全体として O(n log n) で効率的に動作します。

実装例

以下のコードで実際の動作を確認してみましょう。

class Solution:
    def solve(self, intervals):
        intervals.sort()
        ans = []
        for s, e in intervals:
            if ans and s <= ans[-1][1]:
                ans[-1][1] = max(ans[-1][1], e)
            else:
                ans.append([s, e])
        return ans

ob = Solution()
inv = [[2, 5], [4, 10], [20, 25]]
print(ob.solve(inv))

入力

[[2, 5], [4, 10], [20, 25]]

出力

[[2, 10], [20, 25]]

コードのポイント

• ソートが鍵： 区間を開始位置でソートしておくことで、現在の区間と比較すべき相手は常に ans の末尾の区間だけでよくなります。
• 包含関係への対応： max(ans[-1][1], e) を使うことで、ある区間が別の区間に完全に含まれるケース（例：[2, 10] の後に [3, 5] が来る場合）でも正しく処理できます。
• 隣接する区間： 「s == 前の区間の終了位置」も条件 s <= ans[-1][1] に含まれるため、[1, 3] と [3, 5] のような端点で接する区間も [1, 5] にマージされます。接する区間を別々に扱いたい場合は、条件を s < ans[-1][1] に変更してください。