Pythonで重複する区間をマージするアルゴリズムの実装方法

はじめに

区間（インターバル）のコレクションが与えられたとき、重なり合っているすべての区間を1つに統合（マージ）する問題を考えてみましょう。

例えば、区間が [[1,3], [2,6], [8,10], [15,18]] のように与えられた場合、マージ後の結果は [[1,6],[8,10],[15,18]] となります。これは、[1,3] と [2,6] の2つの区間が互いに重なっているため、これらを統合して [1,6] とするからです。

解法のアプローチ

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

• 区間リストの長さが0の場合、空のリストを返す
• クイックソートなどのソート手法を使って、区間リストを開始位置の昇順に並べ替える
• 空のスタックを用意し、最初の区間 intervals[0] をスタックに挿入する
• i を1から区間数-1まで繰り返し処理する
  • スタックの先頭要素を last_element として取得する
  • last_element の終了位置が intervals[i] の開始位置以上である場合（＝重なっている場合）：
    • last_element の終了位置を、「intervals[i] の終了位置」と「last_element の終了位置」の最大値に更新する
    • スタックから先頭要素を取り出し、更新した last_element を再びプッシュする
  • 重なっていない場合は、intervals[i] をそのままスタックにプッシュする
• 最後にスタックを結果として返す

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

実装例

class Solution(object):
   def merge(self, intervals):
      """
      :type intervals: List[Interval]
      :rtype: List[Interval]
      """
      if len(intervals) == 0:
         return []
      self.quicksort(intervals,0,len(intervals)-1)
      stack = []
      stack.append(intervals[0])
      for i in range(1,len(intervals)):
         last_element= stack[len(stack)-1]
         if last_element[1] >= intervals[i][0]:
            last_element[1] = max(intervals[i][1],last_element[1])
            stack.pop(len(stack)-1)
            stack.append(last_element)
         else:
            stack.append(intervals[i])
      return stack
   def partition(self,array,start,end):
      pivot_index = start
      for i in range(start,end):
         if array[i][0]<=array[end][0]:
            array[i],array[pivot_index] =array[pivot_index],array[i]
            pivot_index+=1
      array[end],array[pivot_index] =array[pivot_index],array[end]
      return pivot_index
   def quicksort(self,array,start,end):
      if start<end:
         partition_index = self.partition(array,start,end)
         self.quicksort(array,start,partition_index-1)
         self.quicksort(array, partition_index + 1, end)
ob1 = Solution()
print(ob1.merge([[1,3],[2,6],[8,10],[15,18]]))

入力

[[1,3],[2,6],[8,10],[15,18]]

出力

[[1, 6], [8, 10], [15, 18]]

補足：より簡潔な実装

上記の実装では自前のクイックソートを実装していますが、Pythonでは組み込みの sort() メソッドを使うことで、コードをより簡潔にできます。

def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])  # 開始位置でソート
    merged = [intervals[0]]
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:  # 重なっている場合
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    return merged

計算量について

このアルゴリズムの計算量は以下の通りです。

• 時間計算量： O(n log n) — ソートが支配的なコストとなるため
• 空間計算量： O(n) — 結果を格納するためのリストが必要

区間のマージ問題は、カレンダーの予定管理や会議室の予約システムなど、実務でもよく登場する重要なアルゴリズムです。ぜひマスターしておきましょう。