非洛谷题目,求神犇给个思路
  • 板块题目总版
  • 楼主wula_miao
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/10/30 20:12
  • 上次更新2024/10/30 22:12:17
查看原帖
非洛谷题目,求神犇给个思路
565985
wula_miao楼主2024/10/30 20:12

nn颗星星,每个星星能被观测的时间范围为[si,ti][s_i, t_i]1<=si<=ti1 <= s_i <= t_i,在每一个整数时刻,都可以选择一个可观测星星进行拍摄(第ii颗星星在si,tis_i,t_i这两个时刻也可以被观测到) 现给nn个星星的观测时间范围,问从时刻11开始,最多能拍摄到多少不同的星星?

第一行一个整数n(1<=n<=2105)n(1<=n<=2*10^5),表示星星的个数

接下来nn行,每行两个正整数si,ti(1<=si<=ti<=109)s_i, t_i(1<=s_i<=t_i<=10^9),表示可以在[si,ti][s_i,t_i]内观测到该星星

输出: 一个正整数,表示最多可以拍摄到的不同星星数

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个
按开始时间贪心错误太明显就不写了
2024/10/30 20:12
加载中...