Chương trình tìm tổng độ dài duy nhất từ danh sách khoảng trong Python

Mô tả bài toán

Cho danh sách khoảng [start, end] (bao gồm cả hai đầu). Tìm tổng độ dài duy nhất (không tính chồng lặp) mà các khoảng bao phủ.

Ví dụ: intervals = [[2,11],[13,31],[41,61]] → đầu ra 50 (10+19+21).

Giải thuật (Sắp xếp + Gộp khoảng)

1. Nếu rỗng: trả về 0.
2. Sắp xếp intervals.
3. Khởi tạo start, end = intervals[0], ans = 0.
4. Duyệt các khoảng (s,e):
   • Nếu s > end: cộng end - start + 1 vào ans, cập nhật start, end = s, e.
   • Ngược lại: end = max(end, e).
5. Cộng đoạn cuối: ans += end - start + 1.
6. Trả về ans.

Ví dụ mã Python

class Solution:
    def solve(self, intervals):
        if not intervals:
            return 0
        intervals.sort()
        start, end = intervals[0]
        ans = 0
        for s, e in intervals:
            if s > end:
                ans += end - start + 1
                start = s
                end = e
            else:
                end = max(end, e)
        ans += end - start + 1
        return ans

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

Đầu vào

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

Đầu ra

50