在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的大小，do
  • if start <= end, then
    • 在 ans 中插入区间 [start，end]
  • 如果 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]]