在 Python 中檢查是否有任何區間完全重疊

假設，我們得到一組區間，其中包含值 (a,b)，其中 a 表示事件的開始時間，b 表示事件的結束時間。我們的任務是檢查這些區間中是否有任何區間完全重疊於其他任何區間。如果任何區間重疊，則返回結果 True，否則返回 False。

因此，如果輸入類似於 [(4,6), (10,12), (7,9), (13,16)]，則輸出將為 False。如果輸入類似於 [(4,6), (4,9), (7,11), (5,8)]，則輸出將為 True。

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

• 對區間列表進行排序
• 對於 i 從 1 到區間大小，執行以下操作
  • 如果 intervals[i, 1] <= intervals[i- 1, 1]，則
    • 返回 True
  • 返回 False

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

示例

 即時演示

def solve(intervals):
intervals.sort()
for i in range(1, len(intervals)):
   if intervals[i][1] <= intervals[i- 1][1]:
      return True
   return False
intervals = [(4,6),(10,12),(7,9),(13,16)] 
intervals2 = [(4,6), (4,9), (7,11), (5,8)] 
print(solve(intervals))
print(solve(intervals2))

輸入

[(4,6),(10,12),(7,9),(13,16)] [(4,6), (4,9), (7,11), (5,8)]

輸出

False
True

Arnab Chakraborty

更新於: 2020-12-30

2K+ 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習