有n颗星星,每个星星能被观测的时间范围为[si,ti],1<=si<=ti,在每一个整数时刻,都可以选择一个可观测星星进行拍摄(第i颗星星在si,ti这两个时刻也可以被观测到)
现给n个星星的观测时间范围,问从时刻1开始,最多能拍摄到多少不同的星星?
第一行一个整数n(1<=n<=2∗105),表示星星的个数
接下来n行,每行两个正整数si,ti(1<=si<=ti<=109),表示可以在[si,ti]内观测到该星星
输出:
一个正整数,表示最多可以拍摄到的不同星星数
sample1
input:
4
1 1
1 2
2 2
2 3
output:
3
sample2:
input:
5
2 3
1 2
3 3
3 4
1 5
output:
5
个人用贪心做法分别按开始和结束时间进行排序都没做出来,做法是从时间1开始遍历,每次+1或跳到下一个星星的开始时间,以下是反例:
按结束时间贪心错:
6
1 4
4 4
2 5
5 5
1 6
6 6
实际能拍摄到6个,但结束贪心只能拍到4个
按开始时间贪心错误太明显就不写了