โปรแกรมค้นหาช่วงเวลาที่ทับซ้อนกันและส่งคืนตามลำดับจากน้อยไปมากใน Python

สมมติว่าเรามีรายการช่วงปิดและรายการช่วงอื่น แต่ละรายการจะไม่ทับซ้อนกันและจัดเรียงตามลำดับที่ไม่ลดลง เราต้องหาส่วนที่ทับซ้อนกันของช่วงสองช่วงที่เรียงตามลำดับที่ไม่ลดลง

ดังนั้น หากอินพุตเป็นเหมือน inv1 =[[50, 100],[190, 270],[310, 330]] inv2 =[[40, 120],[180, 190]] ผลลัพธ์จะเป็น [ [50, 100], [190, 190]]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ans :=รายการใหม่
• i :=0, j :=0
• ในขณะที่ i <ขนาด A และ j <ขนาด B ให้ทำ
  • ถ้าเริ่ม <=สิ้นสุด แล้ว
    • แทรกช่วงเวลา [เริ่ม, สิ้นสุด] ลงใน ans
  • ถ้า A[i, 1]
  • ผม :=ผม + 1
• มิฉะนั้น
  • j :=j + 1

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

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