Python程式：查詢插入區間列表中一個可能的最小區間

假設我們有一個名為intervals的二維數字列表，其中每一行表示[開始，結束]（包含）區間。對於區間[a，b]（a < b），其大小為（b - a）。我們必須向給定的列表中新增一個區間，以便在合併所有區間後，我們恰好剩下一個範圍。我們必須找到新增區間的最小可能大小。

因此，如果輸入類似於intervals = [[15, 20],[30, 50]]，則輸出將為10，因為我們可以新增區間[20, 30]，這是最小可能的區間。

為了解決這個問題，我們將遵循以下步驟：

  • events := 新列表
  • 對於intervals中的每個開始和結束時間s、e，執行以下操作：
    • 在events的末尾插入(s, 1)
    • 在events的末尾插入(e, -1)
  • 對列表events進行排序
  • curr_status := 0，last := null
  • 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]

讓我們看看以下實現以獲得更好的理解：

示例

 線上演示

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

更新於: 2020年10月19日

105 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告