Pythonで区間リストを1つの範囲につなぐための最小の挿入区間を求めるプログラム

数値の2次元リスト intervals が与えられ、その各行は [start, end]（両端を含む）という区間を表しているものとします。区間 [a, b]（a < b）のサイズは (b - a) で定義されます。ここで、このリストに区間を1つだけ追加し、すべての区間をマージした結果がちょうど1つの連続した範囲になるようにしたいと考えます。このとき、追加する区間のサイズとしてあり得る最小値を求めるのが本記事の目的です。

例として、入力が intervals = [[15, 20],[30, 50]] の場合を考えてみましょう。このとき出力は 10 になります。[20, 30] という区間を追加すれば、2つの区間がひと続きの範囲につながり、これ以上小さい区間では全体をカバーできないためです。

解決のアプローチ：イベントソートによるスイープ

この問題は、各区間の始点と終点を「イベント」として扱い、時系列順に走査する手法で効率的に解けます。アルゴリズムの手順は以下の通りです。

• events := 新しい空のリスト
• intervals 内の各区間から開始時刻 s と終了時刻 e を取り出し、次の処理を行う
  • (s, 1) を events の末尾に追加（区間の開始イベント）
  • (e, -1) を events の末尾に追加（区間の終了イベント）
• events をソートする
• curr_status := 0、last := None で初期化
• interval := ペア [0, 0]
• events 内の各ペア (time, status) に対して次の処理を行う
  • curr_status が 0 かつ last が存在し、time > last の場合（＝まだ覆われていないギャップが存在する場合）
    • interval[0] が 0 の場合、interval[0] := last（最初のギャップの始点を記録）
    • interval[1] := time（最後のギャップの終点を更新）
  • last := time
  • curr_status := curr_status + status
• interval[1] - interval[0] を返す

このアルゴリズムのポイントは、curr_status が 0 に戻った瞬間に注目することです。ある時刻で被覆数が 0 になり、かつ直前の時刻より先に進んでいるなら、そこに「切れ目」が存在します。最初の切れ目の始点と、最後の切れ目の終点を結んだ区間こそが、すべてのギャップを一度に埋めて全体を1つの範囲にできる最小の区間となります。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
   def solve(self, intervals):
      events = []
      for s, e in intervals:
         events.append((s, 1))
         events.append((e, -1))
      events.sort()
      curr_status = 0
      last = None
      interval = [0, 0]
      for time, status in events:
         if curr_status == 0 and last and time > last:
            if interval[0] == 0:
               interval[0] = last
            interval[1] = time
         last = time
         curr_status += status
      return interval[1] - interval[0]

ob = Solution()
intervals = [[15, 20], [30, 50]]
print(ob.solve(intervals))

入力

[[15, 20],[30, 50]]

出力

10

計算量について

このアルゴリズムでは、n 個の区間から 2n 個のイベントを生成しソートするため、時間計算量は O(n log n)、イベントを格納するための空間計算量は O(n) となります。区間同士を総当たりで比較する方法（O(n²)）よりも高速に動作するのが特徴です。