Gộp Khoảng Giao Dịch CoreBank Vietcombank

Mô tả

Tại ngân hàng Vietcombank, hệ thống CoreBank ghi nhận log thời gian của từng phiên giao dịch trong ngày dưới dạng khoảng [bắt_đầu, kết_thúc]. Do nhiều phiên chạy song song, các khoảng thời gian này thường chồng lấp lên nhau, khiến bộ phận giám sát khó nắm bắt tổng quan.

Trưởng phòng vận hành muốn bạn viết một công cụ tự động gộp mọi khoảng chồng lấp lại thành các khoảng tối giản, sao cho hai khoảng bất kỳ trong kết quả không có điểm chung, và toàn bộ miền thời gian được bao phủ không thay đổi.

Cụ thể: hai khoảng [a, b] và [c, d] được coi là chồng lấp nếu chúng có chung ít nhất một thời điểm, tức c <= b và a <= d. Khi chồng lấp, ta gộp thành [min(a,c), max(b,d)]. Lặp đến khi không còn khoảng nào chồng lấp.

Đầu vào

• Số nguyên n — số lượng khoảng giao dịch.
• n dòng tiếp theo, mỗi dòng ghi hai số nguyên s_i và e_i — thời điểm bắt đầu và kết thúc của khoảng thứ i (s_i <= e_i).

Đầu ra

• Dòng đầu ghi số nguyên m — số khoảng sau khi gộp.
• m dòng tiếp theo, mỗi dòng ghi hai số nguyên cách nhau bởi một dấu cách — khoảng đã gộp, in theo thứ tự bắt đầu tăng dần.

Ràng buộc

• 1 <= n <= 10^5
• 0 <= s_i <= e_i <= 10^9

Ví dụ

Đầu vào:

4 1 3 2 6 8 10 15 18

Đầu ra:

3 1 6 8 10 15 18

Giải thích từng bước:

• Sắp xếp theo bắt đầu: [1,3], [2,6], [8,10], [15,18].
• Xét [1,3] và [2,6]: vì 2 <= 3 nên chồng lấp, gộp thành [1,6].
• Xét [1,6] và [8,10]: vì 8 > 6 nên không chồng, giữ nguyên cả hai.
• Xét [8,10] và [15,18]: vì 15 > 10 nên không chồng, giữ nguyên.
• Kết quả có 3 khoảng: [1,6], [8,10], [15,18].