Python程式：查詢重疊區間並按升序返回

假設我們有一個封閉區間的列表和另一個區間的列表。每個列表在單獨情況下都是非重疊的，並且按非遞減順序排序。我們需要找到這兩個區間的重疊部分，並按非遞減順序排序。

因此，如果輸入類似於 inv1 = [[50, 100],[190, 270],[310, 330]] inv2 = [[40, 120],[180, 190]]，則輸出將為 [[50, 100], [190, 190]]

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

• ans := 一個新的列表
• i := 0, j := 0
• 當 i < A 的大小 且 j < B 的大小 時，執行以下操作：
  • 如果 開始 <= 結束，則：
    • 將區間 [開始, 結束] 插入到 ans 中
  • 如果 A[i, 1] < B[j, 1]，則：
    • i := i + 1
  • 否則：
    • j := j + 1
• 返回 ans

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

示例

 即時演示

class Solution:
   def solve(self, A, B):
      ans = []
      i = 0
      j = 0
      while i < len(A) and j < len(B):
         start = max(A[i][0], B[j][0])
         end = min(A[i][1], B[j][1])
         if start <= end:
            ans.append([start, end])
            if A[i][1] < B[j][1]:
               i += 1
            else:
               j += 1
         return ans
ob = Solution()
inv1 = [[50, 100],[190, 270],[310, 330]]
inv2 = [[40, 120],[180, 190]]
print(ob.solve(inv1, inv2))

輸入

[[50, 100],[190, 270],[310, 330]], [[40, 120],[180, 190]]

輸出

[[50, 100], [190, 190]]

Arnab Chakraborty

更新於: 2020年11月19日

225 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習