C ++中的区间列表交集
假设我们有两个封闭区间的列表,这里每个区间的列表都是成对不相交的,并按排序顺序排列。我们找到了这两个间隔列表的交集。
我们知道闭合间隔[a,b]表示为a<=b。实数集x,其中<=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]]。
为了解决这个问题,我们将遵循以下步骤-
列出列表,设定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
而我<A和j的大小>B的大小
temp:=A[i,0],B[j,0]的最大值,A[i,1]和B[j,1]的最小值
A[i,0]:=温度[1]+1,B[j,0]:=温度[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],B[i])
如果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]]