在 Python 中查詢相交區間

假設我們有一個區間列表，其中每個區間都像 [開始，結束] 這樣表示區間的開始和結束時間（包含），我們需要找到它們的交集，即位於所有給定區間內的區間。

因此，如果輸入類似於 [[10, 110],[20, 60],[25, 75]]，則輸出將為 [25, 60]

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

  • start，end := 從區間列表中刪除最後一個元素後的區間
  • 當 intervals 不為空時，執行以下操作
    • start_temp，end_temp := 從區間列表中刪除最後一個元素後的區間
    • start := start 和 start_temp 的最大值
    • end := end 和 end_temp 的最小值
  • 返回一個區間 [start, end]

讓我們看看下面的實現以更好地理解：

示例

 線上演示

class Solution:
   def solve(self, intervals):
      start, end = intervals.pop()
      while intervals:
         start_temp, end_temp = intervals.pop()
         start = max(start, start_temp)
         end = min(end, end_temp)
      return [start, end]
ob = Solution()
intervals = [[10, 110],[20, 60],[25, 75]]
print(ob.solve(intervals))

輸入

[[10, 110],[20, 60],[25, 75]]

輸出

[25, 60]

更新於：2020-09-23

3K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告