Giao điểm danh sách khoảng thời gian trong C ++

Giả sử chúng ta có hai danh sách các khoảng đã đóng, ở đây mỗi danh sách các khoảng là rời rạc từng cặp và được sắp xếp theo thứ tự. Chúng tôi đã tìm thấy giao điểm của hai danh sách khoảng thời gian này.

Chúng ta biết rằng khoảng đóng [a, b] được ký hiệu là a <=b. tập hợp các số thực x với a <=x <=b. Giao của hai khoảng đóng là tập hợp các số thực rỗng hoặc có thể được biểu diễn dưới dạng một khoảng đóng.

Vì vậy, nếu đầu vào giống như A =[[0,2], [5,10], [13,23], [24,25]] và B =[[1,5], [8,12], [ 15,24], [25,27]], thì đầu ra sẽ là [[1,2], [5,5], [8,10], [15,23], [24,24], [25 , 25]].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một danh sách res, đặt I:=0 và j:=0

• Xác định một phương thức có tên là giao nhau (), phương thức này sẽ nhận a và b -

• nếu a [0] <=b [0] và a [1]> =b [0], thì trả về true,

• ngược lại khi b [0] <=a [0] và b [1]> =a [0] thì trả về true, ngược lại trả về False

• trong khi I size of B

  • nếu giao nhau (A [i], B [i])

    • temp:=tối đa của A [i, 0], B [j, 0], tối thiểu là A [i, 1] và B [j, 1]

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

    • nếu A [i, 0]> A [i, 1] hoặc A [i, 1] <=temp [0], thì hãy tăng i lên 1

    • if B [j, 0]> B [j, 1] or B [j, 1] <=temp [0]:sau đó tăng j lên 1

    • result.append (tạm thời)

    • Bỏ qua cho lần lặp tiếp theo

  • nếu A [i, 0]> B [j, 1] thì tăng j lên 1, nếu không thì tăng i lên 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

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

Đầu ra

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