Bắn bóng bay

Buổi 12 — Greedy Algorithm greedy sorting
Points
19
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$
Draft saved