Hợp Nhất Khoảng Thời Gian

Buổi 65-66 — Mock HSG Data-structures sorting
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$.
Draft saved