[算法题]安排会议室——贪心算法的应用


题目描述

[题目描述]

在大公司里,会议是很多的,开会得有场子,要场子你得先在电子流里预订。 如果你是项目组新来的小弟,那么恭喜你,每天抢订会议室的任务就光荣的分给你了。 老大要求你尽可能多的订会议室,但是这些会议室之间不能有时间冲突。 [Input] input文件中可以包括多个测试案例。 T(T ≤ 20),输入文件的第一行表示文件中有多少个测试案例。 N(1 ≤ N ≤ 500),每个测试案例的第一行表示会议室的数目。 每个测试案例中,除第一行以外表示各个会议室的信息。每行会有3个数字,分别表示会议编号、会议起始时间、会议结束时间。 [Output] 输出可以安排的最大会议数目 [I/O Example] Input 2 6 1 1 10 2 5 6 3 13 15 4 14 17 5 8 14 6 3 12 15 1 4 8 2 2 5 3 2 6 4 4 6 5 2 3 6 1 6 7 4 7 8 3 5 9 3 8 10 1 2 11 1 7 12 2 4 13 5 6 14 4 5 15 7 8 Output 3 5

练习模板 
#include<cstdio>
#include<iostream>

using namespacestd;

intmain(intargc,char**argv)
{
 inttc,T;
cin>>T;
 for(tc=0;tc<T;tc++)
{
 //TODOhere
}

 return 0;//Yourprogramshouldreturn0onnormaltermination.
}

代码实现

题目中要求会议时间不可以冲突,所以可以利用贪心算法,尽可能的选择会议时间结束较早的会议室,这样就能安排最多的会议室。

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>

using namespacestd;


classMeetingRoom{
public:
 intindex;
 intstart;
 intend;
public:
MeetingRoom(inti,ints,inte):index(i),start(s),end(e){}
};

boolisEndEarly(constMeetingRoomr1,constMeetingRoomr2){
 return(r1.end<r2.end);
}

intmain(intargc,char**argv)
{
 inttc,T;
 intnum=0;
 intcount=0;
 intindex=0;
 intstart=0;
 intend=0;
vector<MeetingRoom>rooms;

freopen("input.txt","r",stdin);
cin>>T;
 for(tc=0;tc<T;tc++)
{
rooms.clear();//clearvector

 //getalltheinfoofrooms
cin>>num;
 for(inti=0;i<num;i++){
cin>>index>>start>>end;
MeetingRoomroom(index,start,end);
rooms.push_back(room);
}

 //sortroomsforendtime
sort(rooms.begin(),rooms.end(),isEndEarly);

 //usegreedyalgorithmtosolvepromblem
count=1;
MeetingRoomprev=rooms[0];
 for(vector<MeetingRoom>::iteratorit=rooms.begin()+1;it!=rooms.end();it++){
MeetingRoomcurrent=*it;
 if(current.start>=prev.end){
count++;
prev=current;
}
}

cout<<count<<endl;
}

 return 0;
}
优质内容筛选与推荐>>
1、python yield
2、诊断一句SQL不走索引的原因
3、magento connect中我常用的key和magento网站收集
4、计算几何与计算机图形学方面的一些资源及源代码
5、CSS块级元素、内联元素概念


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号