普及⏱ 1000ms💾 256MB#P5056

题目描述

数轴上飞着 $n$ 只气球,第 $i$ 只占据水平区间 $[l_i, r_i]$。一支箭沿竖直方向射出,能爆掉所有覆盖该横坐标的气球。气球是点目标——只要箭的横坐标落在区间内即可。求引爆全部气球所需的最少箭数。

输入格式

第一行整数 $n$;接下来 $n$ 行每行两个整数 $l, r$

输出格式

一行一个整数。

数据范围

$$1 \le n \le 10^5,\ 0 \le l \le r \le 10^9$$

样例输入 #1
1
5 5
样例输出 #1
1
样例输入 #2
2
1 5
2 6
样例输出 #2
1