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 的大小
if intersect(A[i], B[i])
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
if 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]]
