Problem C: *射箭击气球
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:cccwsz
Submit:55
Solved:25
Description
嘉年华游园会上有"射箭击气球"的项目。是在一个高平台上,前后左右用绳线系着大小不同的气球,让游客们用箭去射。对于每个气球,提供输入的是水平方向上气球直径的左端和右端坐标。布置气球时调整好了绳线长度,使得气球圆心位置的高度是一致的,所以纵坐标并不重要,因此只要知道左端和右端的横坐标就足够了。
你的任务是选择在横坐标 x 处射出一支箭,若有一个气球直径的左端和右端坐标为[xleft,xright], 且满足 xleft ≤ x ≤ xright,则该气球会被引爆。求所有气球被射爆,所需要箭的最小数量。
两个气球挨在一起不重叠,如两个气球的左端与右端位置为[1,3][3,5],那么箭从中穿过也可以一起射爆这两个气球。可见下面样例数据的俯视图示:
Input
第一行一个正整数 n,,表示共有 n个气球。以下 n 行,每行两个数,为每一个气球左端和右端的坐标。
Output
输出一个数,为射爆所有气球所需要的最少箭的数量。
Sample Input Copy
7
1 4
2 6
3 7
7 11
9 13
9 12
11 14
Sample Output Copy
2
HINT
2=<n<=10^5,xleft与xright<=10^9,满足xleft ≤ x ≤ xright。