Ghép Đoạn Chồng Lấn
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Cho $N$ đoạn trên trục số, đoạn thứ $i$ có hai đầu mút $L_i$ và $R_i$ ($L_i \le R_i$). Hãy gộp các đoạn chồng lấn hoặc liền kề lại và in ra các đoạn kết quả theo thứ tự tăng dần.
Hai đoạn $[a, b]$ và $[c, d]$ được coi là chồng lấn hoặc liền kề nếu $c \le b + 1$ và $a \le d + 1$ (sau khi sắp xếp sao cho $a \le c$).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $N$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L_i$ và $R_i$.
Dữ liệu ra
- Dòng đầu tiên in ra số lượng đoạn sau khi gộp.
- Các dòng tiếp theo, mỗi dòng in hai số nguyên là hai đầu mút của một đoạ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$
- $|L_i|, |R_i| \le 10^9$
Community Discussion