Pythonの間隔リストに挿入する可能性のある最小間隔を1つ見つけるプログラム

各行が[開始、終了]（両端を含む）間隔を表す間隔と呼ばれる数値の2Dリストがあるとします。区間[a、b]（a

したがって、入力がintervals =[[15、20]、[30、50]]のような場合、可能な最小の間隔である間隔[20、30]を追加できるため、出力は10になります。

これを解決するには、次の手順に従います-

• イベント：=新しいリスト
• 開始時間と終了時間sごとに、間隔を空けて、
  • イベントの最後に（s、1）を挿入
  • イベントの最後に（e、-1）を挿入します
• リストイベントを並べ替える
• curr_status：=0、last：=null
• 間隔：=ペア[0、0]
• イベントの各ペア（時間、ステータス）について、
  • curr_statusが0と同じで、lastとtime> lastの場合、
    • interval [0]が0と同じ場合、
      • 間隔[0]：=最後
    • 間隔[1]：=時間
  • 最後：=時間
  • curr_status：=curr_status + status
• return interval [1] --interval [0]

理解を深めるために、次の実装を見てみましょう-

例

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