Python程式：合併目標區間查詢區間

假設我們有一列不重疊的區間。這些區間按結束時間排序。我們還有一個目標區間，找到合併目標區間後的最終區間，以便區間仍然不重疊且排序。

因此，如果輸入類似於 intervals = [[1, 15],[25, 35],[75, 90]]，target = [10, 30]，則輸出將為 [[1, 35], [75, 90]]，因為前兩個區間 [1, 15] 和 [25, 35] 已合併。

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

• 將目標區間插入到iv的末尾

• 根據起始時間對iv進行排序

• res := 一個包含第一個區間的新列表

• i := 1

• 當 i < iv 的大小 時，執行以下操作：

  • 如果 iv[i] 的起始時間 <= res 的最後一個區間的結束時間，則

    • res 的最後一個區間的結束時間 = (res 的最後一個區間的結束時間和 iv[i] 的結束時間)中的最大值

  • 否則：

    • 將 iv[i] 插入到 res 的末尾

  • i := i + 1

• 返回 res

示例 (Python)

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

 線上演示

class Solution:
   def solve(self, iv, target):
      iv.append(target)
      iv.sort(key=lambda x: x[0])
      res = [iv[0]]
      i = 1
      while i < len(iv):
         if iv[i][0] <= res[-1][1]:
            res[-1][1] = max(res[-1][1], iv[i][1])
         else:
            res.append(iv[i])
         i += 1
      return res
ob = Solution()
intervals = [
   [1, 15],
   [25, 35],
   [75, 90]
]
target = [10, 30]
print(ob.solve(intervals, target))

輸入

[[1, 15],[25, 35],[75, 90]], [10, 30]

輸出

[[1, 35], [75, 90]]

Arnab Chakraborty

更新於：2020年12月22日

112 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始