C++での区間リストの共通部分

閉じた区間のリストが2つあるとします。ここでは、区間の各リストはペアごとに互いに素であり、ソートされた順序になっています。これら2つの間隔リストの共通部分を見つけました。

閉区間[a、b]はa<=bとして表されることがわかっています。 a <=x<=bの実数xのセット。 2つの閉じた区間の共通部分は、空であるか、閉じた区間として表すことができる実数のセットです。

したがって、入力が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

  を設定します。

• 交差（）と呼ばれるメソッドを定義します。これにはaとbが必要です-

• a [0] <=b[0]およびa[1]>=b [0]の場合、trueを返します

• それ以外の場合、b [0] <=a[0]およびb[1]>=a [0]の場合はtrueを返し、それ以外の場合はFalseを返します

• IBのサイズ

  • 交差する場合（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

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