大家好，欢迎来到IT知识分享网。
1422：活动安排
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交,则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。选择出由相互兼容的活动组成的最大集合。
【输入】
第1行一个整数n(n≤1000)，接下来n行，每行两个整数si和fi。
【输出】
输出尽可能多的互相兼容的活动个数。
【输入样例】
4
1 3
4 6
2 5
1 7
【输出样例】
2
贪心思路：
1. 按照结束时间进行从小到大的排序
2. 第一个结束的活动必选
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/144964.html
