Bắn bóng bay
Points
19
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Trên trục số $Ox$ có $N$ quả bóng bay hình tròn được treo ngang, quả bóng thứ $i$ chiếm đoạn $[l_i, r_i]$. Một mũi tên bắn thẳng đứng tại tọa độ $x$ sẽ làm vỡ mọi quả bóng bay mà $l_i \le x \le r_i$. Hãy tìm số lượng mũi tên ít nhất cần bắn để làm vỡ tất cả $N$ quả bóng bay.
Dữ liệu vào
- Dòng đầu tiên 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
Một số nguyên duy nhất là số mũi tên ít nhất cần dùng.
Ví dụ
| Input | Output |
|---|---|
| 4\n10 16\n2 8\n1 6\n7 12 | 2 |
| 4\n1 2\n3 4\n5 6\n7 8 | 4 |
Giới hạn
- $1 \le N \le 10^5$
- $-10^9 \le l_i \le r_i \le 10^9$
Community Discussion