CSU 1757: 火车入站(区间覆盖的最大覆盖深度)

举报
用户已注销 发表于 2021/11/19 04:00:53 2021/11/19
【摘要】 题目: Description 火车站人们总是在站台等待列车进站,一个站台有火车停留的时候就不能有其他火车进入,今天有n辆火车经过,已知它们进站时间Si以及出站时间Ti,进站时间到出站时间之间火车必须有一个站台给它停靠,问让所有火车都能按时停靠,至少要安排多少个站台给这些火车 Input 第一行输入一个正整数T,表示数据...

题目:

Description

火车站人们总是在站台等待列车进站,一个站台有火车停留的时候就不能有其他火车进入,今天有n辆火车经过,已知它们进站时间Si以及出站时间Ti,进站时间到出站时间之间火车必须有一个站台给它停靠,问让所有火车都能按时停靠,至少要安排多少个站台给这些火车

Input

第一行输入一个正整数T,表示数据组数
每组数据第一行输入一个正整数n,表示火车数量(n<=10000)
接下来n行,每行输入2个正整数Si,Ti,表示第i辆火车的进站时间和出站时间(Si<Ti<1e9)

Output

每组数据输出至少需要安排多少个站台

Sample Input

1
3
1 3
3 4
4 6

Sample Output

2


思路:

其实就是n个闭区间,求一个点最多被多少个区间覆盖

代码:


  
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<algorithm>
  4. using namespace std;
  5. int main()
  6. {
  7. int T, n, s[10001], t[10001];
  8. cin >> T;
  9. while (T--)
  10. {
  11. cin >> n;
  12. for (int i = 1; i <= n; i++)scanf("%d%d", &s[i], &t[i]);
  13. sort(s + 1, s + n + 1);
  14. sort(t + 1, t + n + 1);
  15. int ans = 0;
  16. for (int i = 1, j = 1; i <= n;)
  17. {
  18. if (s[i] <= t[j])
  19. {
  20. if (ans < i - j)ans = i - j;
  21. i++;
  22. }
  23. else j++;
  24. }
  25. cout << ans + 1 << endl;
  26. }
  27. return 0;
  28. }


文章来源: blog.csdn.net,作者:csuzhucong,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nameofcsdn/article/details/79855932

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。