C++ 中的区间列表交集

假设我们有两个封闭区间列表，这里每个区间列表都是成对不相交且已排序的。我们需要找到这两个区间列表的交集。

我们知道封闭区间[a, b]表示为 a <= b，即实数集 x 满足 a <= x <= b。两个封闭区间的交集是一个实数集，它要么为空，要么可以表示为一个封闭区间。

因此，如果输入类似于 A = [[0,2],[5,10],[13,23],[24,25]] 和 B = [[1,5],[8,12],[15,24],[25,27]]，则输出将为 [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]。

为了解决这个问题，我们将遵循以下步骤：

  • 创建一个列表 res，设置 I := 0 和 j := 0

  • 定义一个名为 intersect() 的方法，它将接收 a 和 b：

  • 如果 a[0] <= b[0] 且 a[1] >= b[0]，则返回 true；

  • 否则，如果 b[0] <= a[0] 且 b[1] >= a[0]，则返回 true；否则返回 false。

  • 当 I < A 的大小 且 j < B 的大小 时

    • 如果 intersect(A[i], B[j])

      • temp := A[i, 0]、B[j, 0] 的最大值，A[i,1] 和 B[j, 1] 的最小值

      • A[i,0] := temp[1] + 1, B[j,0] := temp[1] + 1

      • 如果 A[i,0] > A[i,1] 或 A[i,1] <= temp[0]，则将 i 加 1

      • 如果 B[j,0] > B[j,1] 或 B[j,1] <= temp[0]，则将 j 加 1

      • result.append(temp)

      • 跳过下一次迭代

    • 如果 A[i,0] > B[j, 1]，则将 j 加 1，否则将 i 加 1

让我们看看下面的实现以更好地理解：

示例

在线演示

class Solution(object):
   def intervalIntersection(self, A, B):
   result = []
   i,j = 0,0
   while i < len(A) and j < len(B):
      if self.intersect(A[i],B[j]):
         temp = [max(A[i][0],B[j][0]),min(A[i][1],B[j][1])]
         A[i][0]=temp[1]+1
         B[j][0] = temp[1]+1
         if A[i][0] > A[i][1] or A[i][1] <= temp[0]:
            i+=1
         if B[j][0]>B[j][1] or B[j][1] <= temp[0]:
            j+=1
         result.append(temp)
         continue
      if A[i][0]>B[j][1]:
         j+=1
      else:
         i+=1
   return result
   def intersect(self,a,b):
      if a[0]<=b[0] and a[1]>=b[0]:
         return True
      if b[0]<=a[0] and b[1] >=a[0]:
         return True
      return False
ob = Solution()
print(ob.intervalIntersection([[0,2],[5,10],[13,23],[24,25]],[[1,5],[8,12],[15,24],[25,27]]))

输入

[[0,2],[5,10],[13,23],[24,25]]
[[1,5],[8,12],[15,24],[25,27]]

输出

[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

更新于：2020年5月2日

230 次查看

启动你的职业生涯

完成课程获得认证

开始学习
广告