Python程式：計算完全包含在其他區間內的區間數量

假設我們有一列區間。在這個列表中，interval[i] 包含 [start, end] 值。我們必須找到被另一個區間包含的區間數量。如果一個區間被多個其他區間包含，則只應計算一次。當 s0 ≤ s1 且 e0 ≥ e1 時，區間 [s0, e0] 位於另一個區間 [s1, e1] 內。

因此，如果輸入類似於 intervals = [[2, 6],[3, 4],[4, 7],[5, 5]]，則輸出將為 2，因為 [3, 4] 和 [5, 5] 分別位於 [2, 6] 和 [4, 7] 內。

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

  • 如果 intervals 列表為空，則
    • 返回 0
  • 根據開始時間對 intervals 列表進行排序，當開始時間相同時，按結束時間的降序排列
  • end_mx := -∞
  • ans := 0
  • 對於 intervals 中的每個 (start, end) 對，執行以下操作：
    • 如果 end <= end_mx，則
      • ans := ans + 1
    • end_mx := end_mx 和 end 的最大值
  • 返回 ans

示例

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

def solve(intervals):
   if not intervals:
      return 0

   intervals.sort(key=lambda x: (x[0], -x[1]))

   end_mx = float("-inf")
   ans = 0

   for start, end in intervals:
      if end <= end_mx:
         ans += 1

      end_mx = max(end_mx, end)

   return ans

intervals = [[2, 6],[3, 4],[4, 7],[5, 5]]
print(solve(intervals))

輸入

[[2, 6],[3, 4],[4, 7],[5, 5]]

輸出

2

更新於：2021年10月18日

438 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告