Chương trình tìm các khoảng không giao với khoảng cắt trong Python

Mô tả bài toán

Cho danh sách khoảng intervals đã sắp xếp và không chồng chéo, và một khoảng cut. Xóa tất cả phần giao của các khoảng với cut, trả về danh sách khoảng còn lại.

Ví dụ: intervals = [[2,11],[13,31],[41,61]], cut = [8,46] → đầu ra [[2,8], [46,61]].

Giải thuật (Xử lý từng khoảng)

1. cut_start, cut_end = cut.
2. Khởi tạo ans = [].
3. Duyệt mỗi khoảng (start, end):
   • Nếu max(cut_start, start) < min(end, cut_end) (có giao):
     • Nếu start < cut_start: thêm [start, cut_start].
     • Nếu end > cut_end: thêm [cut_end, end].
   • Ngược lại: thêm nguyên khoảng [start, end].
4. Trả về ans.

Ví dụ mã Python

class Solution:
    def solve(self, intervals, cut):
        cut_start, cut_end = cut
        ans = []
        for start, end in intervals:
            if max(cut_start, start) < min(end, cut_end):
                if start < cut_start:
                    ans.append([start, cut_start])
                if end > cut_end:
                    ans.append([cut_end, end])
            else:
                ans.append([start, end])
        return ans

ob = Solution()
intervals = [[2, 11], [13, 31], [41, 61]]
cut = [8, 46]
print(ob.solve(intervals, cut))

Đầu vào

[[2, 11],[13, 31],[41, 61]], [8, 46]

Đầu ra

[[2, 8], [46, 61]]