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]]

更新于: 2020年11月19日

225 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告