Ghép Đoạn Chồng Lấn

Algorithms Buổi 10 — STL Algorithms Implementation sorting
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$
Draft saved