Mô tả
Ban Quản lý đường cao tốc Hà Nội - Hải Phòng đang tiến hành rà soát và tối ưu hóa hệ thống trạm thu phí trên tuyến. Hiện tại, nhiều trạm thu phí tạm thời được thiết lập để thu phí từng đoạn đường riêng biệt. Do quá trình mở rộng, các trạm này có vùng hoạt động chồng lấp lên nhau.
Ví dụ, một trạm hoạt động từ km 10 đến km 30, trong khi một trạm khác lại hoạt động từ km 20 đến km 40. Việc duy trì hai trạm này gây lãng phí chi phí vận hành. Do đó, ban quản lý yêu cầu gom các trạm có vùng hoạt động chồng lấp hoặc liền kề lại thành một trạm duy nhất.
Bạn được cho danh sách n trạm thu phí, mỗi trạm được mô tả bằng một đoạn cao tốc [start, end] (đơn vị tính bằng km). Nhiệm vụ của bạn là gom tất cả các đoạn giao nhau hoặc chạm nhau (điểm cuối của đoạn này bằng điểm đầu của đoạn kia) lại, và trả về danh sách các đoạn cao tốc đã được gom tối giản.
Quy ước:
- Hai đoạn
[1, 5]và[5, 10]được xem là chạm nhau và sẽ được gom thành[1, 10]. - Hai đoạn
[1, 5]và[6, 10]là rời nhau (từ km 5 đến km 6 có khoảng trống) và sẽ được giữ nguyên độc lập. - Kết quả trả về phải được sắp xếp theo thứ tự điểm bắt đầu tăng dần.
Đầu vào
- Dòng 1: Số nguyên
n(1 ≤ n ≤ 10^4) — số lượng trạm thu phí. ndòng tiếp theo, mỗi dòng chứa hai số nguyênstartvàend(0 ≤ start < end ≤ 10^9) mô tả một đoạn cao tốc.
Đầu ra
- Dòng 1: Số nguyên
m— số lượng trạm thu phí sau khi gom.