โปรแกรมหา overlapping intervals ของสองชุดใน Python

สมมติว่ามี 2 ชุด intervals ที่แต่ละชุดไม่ทับซ้อนในตัวเองและเรียงแล้ว ต้องการหา intersection ของทั้งสองชุด เรียงลำดับ

ตัวอย่าง: inv1 = [[50,100],[190,270],[310,330]], inv2 = [[40,120],[180,190]] ผลลัพธ์ [[50,100],[190,190]]

ขั้นตอนการแก้ปัญหา

1. ans = [], i = 0, j = 0
2. วนลูป بينما i < len(A) and j < len(B):
   • start = max(A[i][0], B[j][0]), end = min(A[i][1], B[j][1])
   • ถ้า start <= end: เพิ่ม [start,end] เข้า ans
   • ถ้า A[i][1] < B[j][1]: i += 1 มิฉะนั้น j += 1
3. คืน ans

ตัวอย่างโค้ด

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