Chương trình hợp nhất khoảng thời gian với khoảng mục tiêu trong Python

Cho danh sách khoảng thời gian không giao nhau, đã sắp xếp theo thời gian kết thúc. Cho khoảng target, chèn và hợp nhất để danh sách vẫn không giao nhau và sắp xếp.

Ví dụ: intervals=[[1,15],[25,35],[75,90]], target=[10,30] → [[1,35],[75,90]].

Giải thuật (Chèn + Sắp xếp + Hợp nhất tuyến tính)

1. Thêm target vào danh sách.
2. Sắp xếp theo thời gian bắt đầu.
3. Duyệt: nếu khoảng hiện tại giao với cuối res → hợp nhất (cập nhật end = max). Ngược lại → thêm mới.

Ví dụ minh họa

class Solution:
    def solve(self, iv, target):
        iv.append(target)
        iv.sort(key=lambda x: x[0])
        res = [iv[0]]
        for i in range(1, len(iv)):
            if iv[i][0] <= res[-1][1]:
                res[-1][1] = max(res[-1][1], iv[i][1])
            else:
                res.append(iv[i])
        return res

ob = Solution()
intervals = [[1,15],[25,35],[75,90]]
target = [10,30]
print(ob.solve(intervals, target))  # Output: [[1, 35], [75, 90]]

Đầu vào / Đầu ra

Input: [[1,15],[25,35],[75,90]], [10,30]

Output: [[1, 35], [75, 90]]