Hợp Nhất Khoảng Thời Gian
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho $N$ khoảng thời gian dạng $[L_i, R_i]$. Hãy hợp nhất tất cả các khoảng giao nhau hoặc chạm nhau (hai khoảng $[a, b]$ và $[c, d]$ với $c \le b$ hợp nhất thành $[a, \max(b, d)]$) và tính tổng độ dài của các khoảng sau khi hợp nhất.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$.
- $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L_i, R_i$.
Dữ liệu ra
In ra số lượng khoảng sau khi hợp nhất và tổng độ dài của chúng (cách nhau bởi dấu cách).
Ví dụ
| Input | Output |
|---|---|
| 4 1 4 3 6 8 10 10 12 |
2 9 |
Giới hạn
- $1 \le N \le 10^5$.
- $-10^9 \le L_i \le R_i \le 10^9$.
Community Discussion