1323：【例6.5】活动选择
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 10673 通过数: 5828
【题目描述】
学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。
现在给出n个活动使用礼堂的起始时间 begini 和结束时间 endi(begini
【输入】
第一行一个整数n(n≤1000)；
接下来的n行，每行两个整数，第一个begini，第二个是endi(begini
【输出】
输出最多能安排的活动个数。
【输入样例】
113 51 412 148 120 68 116 105 73 85 92 13
【输出样例】
4
【分析】
算法模型∶给 n 个开区间（begini，endi），选择尽量多的区间，使得两两不交。
做法：首先按照 endl<=end2<=…<=endn 的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。
正确性：如果不选 endl，假设第一个选择的是endi，则如果 endi 和 end1 不交叉则多选一个 end1 更划算；如果交叉则把 endi 换成 end1 不影响后续选择。
【参考代码】
#include <stdio.h>#define N 1010struct schedule{int begin;//开始时间 int end; //结束时间 }meet[N],t;int main(){int i,j,n,ans=1,record;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d%d",&meet[i].begin,&meet[i].end);for(i=0;i<n-1;i++)//比较排序 { for(j=i+1;j<n;j++){ if(meet[i].end > meet[j].end){t=meet[i];meet[i]=meet[j];meet[j]=t;}}}record=meet[0].end; //第一个结束时间 for(i=1;i<n;i++){if(meet[i].begin >= record) //开始时间不冲突 {ans++;record=meet[i].end;//更新结束时间}}printf("%d\n",ans);return 0;}
:8088/problem_show.php?pid=1323
如果觉得《信息学奥赛一本通（1323：【例6.5】活动选择）》对你有帮助，请点赞、收藏，并留下你的观点哦！
