Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm các khoảng chồng chéo và trả lại chúng theo thứ tự tăng dần trong Python

Giả sử chúng ta có một danh sách các khoảng đã đóng và một danh sách các khoảng khác. Riêng lẻ, mỗi danh sách không chồng chéo và chúng được sắp xếp theo thứ tự không giảm dần. Chúng ta phải tìm sự trùng lặp của hai khoảng được sắp xếp theo thứ tự không giảm.

Vì vậy, nếu đầu vào giống như inv1 =[[50, 100], [190, 270], [310, 330]] inv2 =[[40, 120], [180, 190]], thì đầu ra sẽ là [ [50, 100], [190, 190]]

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

  • ans:=một danh sách mới
  • i:=0, j:=0
  • while i
  • nếu start <=end, thì
    • chèn khoảng thời gian [bắt đầu, kết thúc] vào ans
  • nếu A [i, 1]
  • i:=i + 1
  • nếu không,
    • j:=j + 1
  • trả lại ans

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

    Ví dụ 

    class Solution:
   def solve(self, A, B):
      ans = []
      i = 0
      j = 0
      while i < len(A) and j < len(B):
         start = max(A[i][0], B[j][0])
         end = min(A[i][1], B[j][1])
         if start <= end:
            ans.append([start, end])
            if A[i][1] < B[j][1]:
               i += 1
            else:
               j += 1
         return ans
ob = Solution()
inv1 = [[50, 100],[190, 270],[310, 330]]
inv2 = [[40, 120],[180, 190]]
print(ob.solve(inv1, inv2))

    Đầu vào 

    [[50, 100],[190, 270],[310, 330]], [[40, 120],[180, 190]]

    Đầu ra 

    [[50, 100], [190, 190]]