Gom Dải Phủ Sóng Đài Truyền Hình Cần Thơ

Mô tả

Đài Truyền hình Cần Thơ đang tổ chức lại hệ thống phát sóng trên dải tần số trục số. Mỗi trạm phát sóng quản lý một đoạn liên tục từ tần số L đến tần số R (L ≤ R). Hai trạm được xem là giao nhau nếu đoạn của chúng có chung ít nhất một điểm trên trục số — kể cả khi đầu đoạn trạm này chạm đúng đuôi đoạn trạm kia. Ví dụ đoạn [30, 70] và [70, 120] giao nhau tại điểm 70, do đó chúng phải được gom làm một.

Để tránh trùng lặp tần số và tối ưu lịch phát sóng, ban giám đốc yêu cầu bạn gom tất cả các đoạn giao nhau lại với nhau, mỗi nhóm trở thành một đoạn duy nhất trải từ L nhỏ nhất đến R lớn nhất trong nhóm. Hãy xuất danh sách các đoạn sau khi gom, sắp xếp tăng dần theo đầu mút bên trái.

Đầu vào

• Số nguyên n — số lượng đoạn tần số.
• Ma trận segments gồm n dòng, mỗi dòng gồm hai số nguyên [L, R] mô tả một đoạn.

Đầu ra

• Danh sách các đoạn sau khi gom, mỗi đoạn là một cặp [L, R], sắp xếp tăng dần theo L.

Ràng buộc

• 1 ≤ n ≤ 10^5
• 0 ≤ L ≤ R ≤ 10^9

Ví dụ

Ví dụ 1:

Đầu vào:

n = 4 segments = [[30, 70], [70, 120], [150, 200], [180, 220]]

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

• Sắp xếp theo L: [30,70], [70,120], [150,200], [180,220].
• Bắt đầu với đoạn [30,70], R_hiện = 70.
• Đoạn [70,120] có L=70 ≤ R_hiện=70 → giao nhau → mở rộng thành [30,120], R_hiện = 120.
• Đoạn [150,200] có L=150 > R_hiện=120 → không giao → chốt [30,120], bắt đầu đoạn mới.
• Đoạn [180,220] có L=180 ≤ R_hiện=200 → giao → mở rộng thành [150,220].
• Kết quả: [[30, 120], [150, 220]].

Đầu ra: [[30, 120], [150, 220]]