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