Chương trình gộp khoảng và sắp xếp tăng dần trong Python

Mô tả bài toán

Cho danh sách các khoảng intervals. Gộp các khoảng chồng chéo và trả về danh sách khoảng không chồng chéo, sắp xếp tăng dần.

Ví dụ: inv = [[2,5],[4,10],[20,25]] → đầu ra [[2,10], [20,25]].

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

1. Sắp xếp intervals theo đầu.
2. Khởi tạo ans = [].
3. Duyệt mỗi khoảng (s,e):
   • Nếu ans không rỗng và s <= ans[-1][1]: ans[-1][1] = max(ans[-1][1], e).
   • Ngược lại: thêm [s,e] vào ans.
4. Trả về ans.

Ví dụ mã Python

class Solution:
    def solve(self, intervals):
        intervals.sort()
        ans = []
        for s, e in intervals:
            if ans and s <= ans[-1][1]:
                ans[-1][1] = max(ans[-1][1], e)
            else:
                ans.append([s, e])
        return ans

ob = Solution()
inv = [[2, 5], [4, 10], [20, 25]]
print(ob.solve(inv))

Đầu vào

[[2, 5],[4, 10],[20, 25]]

Đầu ra

[[2, 10], [20, 25]]