3826: 引爆气球的最少箭数
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：20
解决：4
题目描述
在二维平面上有一堵墙，上面悬挂着若干个球形气球。每个气球的水平位置可以用一个区间 [x_start, x_end] 来表示，即气球的直径在x轴上的投影是从 x_start 到 x_end。气球的y坐标忽略不计。
现在我们可以从x轴上的任意点垂直向上射箭。如果箭的x坐标 x 满足 x_start ≤ x ≤ x_end，则该气球会被射中引爆。弓箭可以无限前进，射出的数量没有限制。
请问，给定所有气球的坐标区间，最少需要多少支箭才能引爆所有气球？
输入
第一行包含一个整数 n，表示气球的数量。
接下来 n 行，每行包含两个整数 x_start 和 x_end，表示一个气球的水平直径范围。数据保证 x_start < x_end。
输出
输出一个整数，表示引爆所有气球所需的最少箭数。
样例输入 复制
4
10 16
2 8
1 6
7 12样例输出 复制
2提示
1 ≤ n ≤ 10^5
-2^31 ≤ x_start < x_end ≤ 2^31 - 1