Chương trình tìm khoảng chèn tối thiểu để hợp nhất danh sách khoảng thành một khoảng duy nhất bằng Python

Cho danh sách 2D intervals mỗi hàng là [start, end] (bao gồm cả hai). Kích thước khoảng [a, b] là b - a. Cần thêm một khoảng vào danh sách sao cho sau khi hợp nhất tất cả các khoảng, chỉ còn lại đúng một khoảng. Tìm kích thước nhỏ nhất của khoảng thêm vào.

Ví dụ: intervals = [[15, 20], [30, 50]] → 10 (thêm [20, 30]).

Quy trình giải quyết (Sweep Line)

1. Tạo danh sách sự kiện events: với mỗi (s, e) thêm (s, 1) và (e, -1).
2. Sắp xếp events.
3. Duyệt sự kiện, giữ curr_status (số khoảng đang hoạt động) và last (thời điểm trước).
4. Khi curr_status == 0 và last tồn tại và time > last: cập nhật khoảng trống interval.
5. Trả về interval[1] - interval[0].

Ví dụ mã nguồn

class Solution:
    def solve(self, intervals):
        events = []
        for s, e in intervals:
            events.append((s, 1))
            events.append((e, -1))
        events.sort()
        curr_status = 0
        last = None
        interval = [0, 0]
        for time, status in events:
            if curr_status == 0 and last and time > last:
                if interval[0] == 0:
                    interval[0] = last
                interval[1] = time
            last = time
            curr_status += status
        return interval[1] - interval[0]

ob = Solution()
intervals = [[15, 20], [30, 50]]
print(ob.solve(intervals))  # Output: 10

Đầu vào

[[15, 20], [30, 50]]

Đầu ra

10