Gộp các khoảng thời gian chồng lấn
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Cho $N$ khoảng thời gian đóng $[L_i, R_i]$. Hai khoảng có thể được gộp thành một khoảng duy nhất nếu chúng giao nhau (kể cả trường hợp chạm đầu mút, tức $L_j \le R_i$ với $L_i \le L_j$).
Hãy gộp tất cả các khoảng chồng lấn lại và in ra danh sách các khoảng rời nhau kết quả theo thứ tự tăng dần của đầu mút trái.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L_i, R_i$ ($-10^9 \le L_i \le R_i \le 10^9$).
Dữ liệu ra
- Dòng đầu tiên in ra số lượng khoảng sau khi gộp $M$.
- $M$ dòng tiếp theo, mỗi dòng in ra hai số nguyên $L, R$ của khoảng tương ứng theo thứ tự tăng dần.
Ví dụ
| Input | Output |
|---|---|
| 4 1 3 2 6 8 10 15 18 |
3 1 6 8 10 15 18 |
Giới hạn
- $1 \le N \le 10^5$
- $-10^9 \le L_i \le R_i \le 10^9$
Community Discussion