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

Mô tả bài toán

Cho danh sách các khoảng [start, end]. Gộp các khoảng chồng chéo và tìm độ dài khoảng lớn nhất sau khi gộp.

Ví dụ: [[1,6],[4,9],[5,6],[11,14],[16,20]] → đầu ra 9 (khoảng [1,9] độ dài 9).

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

1. Sắp xếp danh sách khoảng.
2. Khởi tạo union = intervals[0], best = union[1] - union[0] + 1.
3. Duyệt các khoảng còn lại:
   • Nếu start <= union[1]: mở rộng union[1] = max(union[1], end).
   • Ngược lại: union = [start, end].
   • Cập nhật best = max(best, union[1] - union[0] + 1).
4. Trả về best.

Ví dụ mã Python

class Solution:
    def solve(self, intervals):
        intervals.sort()
        union = intervals[0]
        best = union[1] - union[0] + 1
        for s, e in intervals[1:]:
            if s <= union[1]:
                union[1] = max(union[1], e)
            else:
                union = [s, e]
            best = max(best, union[1] - union[0] + 1)
        return best

ob = Solution()
intervals = [[1, 6], [4, 9], [5, 6], [11, 14], [16, 20]]
print(ob.solve(intervals))

Đầu vào

[[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]

Đầu ra

9