ACM_区间调度问题(贪心)
2024-08-26 05:44:21
Meetings 系列一
Time Limit: 2000/1000ms (Java/Others)
Problem Description:
多年之后的广财ACM编协如日中天,下系多个部门,且编协成员几近过百。这一次,为了庆祝ACM编协近年飞速的发展,各部门都决定在同一天召开会议。请注意:这次由于资源紧张,仅申请到一个报告厅。现在需要你给出安排方案,使得同一天24小时内举行的会议场次尽可能多。
为了简化问题,作如下规定:
(1)每一场会议M(a,b)表示从a时刻开始,b时刻结束(其中,a,b都为整数且8 <= a < b <= 20);
(2)同一时段内报告厅仅允许一个部门进行开会,不同部门交接时可忽略不同场次交换耗费的时间。
Input:
输入包含多组测试数据,每组数据第一行输入整数n(0<n<=20)表示一共有n场会议要安排。下面n行依次输入每一场会议的开始跟结束时刻a,b。
Output:
每一组测试输出可以安排的场次的最大数目,占一行。
Sample Input:
3
12 15
12 13
14 18
5
11 12
13 18
18 20
13 16
16 17
Sample Output:
2
4
解题思路:贪心策略:将所有区间按右端点坐标(结束时间)从小到大排序,顺序处理每个区间。如果它与当前已选的所有区间都没有重叠,则选择该区间,否则不选。注意:起始时间和结束时间在8-20范围内。
算法证明--->博主:阳光日志
AC代码:
#include<bits/stdc++.h>
using namespace std;
struct NODE{
int st,ed;
}node[];
bool cmp(NODE x,NODE y){
return x.ed<y.ed; //按结束时间早的升序排
}
int main()
{
int n,num,k,t,s,e;
while(cin>>n){
k=-;
for(int i=;i<=n;++i){
cin>>s>>e;
if(s>= && e<=){node[++k].st=s;node[k].ed=e;}
}
sort(node,node+k+,cmp);
num=t=;
for(int i=;i<=k;++i)
if(t<=node[i].st){num++;t=node[i].ed;}
cout<<num<<endl;
}
return ;
}
也可以使用STL中的pair<int,int>。AC代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,num,k,t,s,e;pair<int,int> itv[];
while(cin>>n){
k=-;
for(int i=;i<=n;++i){ //second记录起始时间,first记录结束时间
cin>>s>>e; //这样就按照结束时间早的升序排
if(s>= && e<=){itv[++k].second=s;itv[k].first=e;}
}
sort(itv,itv+k+);num=t=;
for(int i=;i<=k;++i)
if(t<=itv[i].second){num++;t=itv[i].first;}
cout<<num<<endl;
}
return ;
}
最新文章
- js,addEventListener参数传递
- html中获取图片的真实尺寸
- DB2 表空间和缓冲池
- 射频识别技术漫谈(9)&mdash;&mdash;动物标签HDX【worldsing笔记】
- 210 - Concurrency Simulator(WF1991, deque, 模拟)
- pat 1062. Talent and Virtue (25)
- mysql出现错误“ Every derived table must have its own alias”
- MongoDB 启动异常
- typedef,static,const用法
- oracle与sqlserver区别
- margin属性的正负值确定
- amaze UI 笔记 - JS
- eclipse jpa 工具生成实体类
- Spark操作HBase报:org.apache.hadoop.hbase.client.RetriesExhaustedWithDetailsException异常解决方案
- 在CentOS下的docker容器中部署spring boot应用的两种方式
- decorator, async/await, generator
- 微信h5支付“网站域名ICP备案主体与商户号主体不一致”的解决方法,H5微信支付 授权函下载
- vue项目中, 字段信息为空时不渲染,是真的不渲染吗
- Win7 访问win2008 远程桌面提示:您的凭证不工作
- MVC3学习:利用mvc3+ajax实现全选和批量删除