[算法题]安排会议室——贪心算法的应用
题目描述
[题目描述]
在大公司里,会议是很多的,开会得有场子,要场子你得先在电子流里预订。 如果你是项目组新来的小弟,那么恭喜你,每天抢订会议室的任务就光荣的分给你了。 老大要求你尽可能多的订会议室,但是这些会议室之间不能有时间冲突。 [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; }优质内容筛选与推荐>>