Chương trình tìm giao của hai tập hợp khoảng đã sắp xếp trong Python

Mô tả bài toán

Cho hai danh sách khoảng A và B, mỗi danh sách không chồng chéo nội bộ và đã sắp xếp. Tìm giao của hai tập hợp khoảng, kết quả cũng không chồng chéo và sắp xếp.

Ví dụ: inv1 = [[50,100],[190,270],[310,330]], inv2 = [[40,120],[180,190]] → đầu ra [[50,100], [190,190]].

Giải thuật (Hai con trỏ)

1. Khởi tạo ans = [], i = 0, j = 0.
2. Khi i < len(A) và j < len(B):
   • start = max(A[i][0], B[j][0]), end = min(A[i][1], B[j][1]).
   • Nếu start <= end: thêm [start, end] vào ans.
   • Nếu A[i][1] < B[j][1]: i += 1; ngược lại j += 1.
3. Trả về ans.

Ví dụ mã Python

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