[题目描述]
在大公司里，会议是很多的，开会得有场子，要场子你得先在电子流里预订。如果你是项目组新来的小弟，那么恭喜你，每天抢订会议室的任务就光荣的分给你了。老大要求你尽可能多的订会议室，但是这些会议室之间不能有时间冲突。[Input]input文件中可以包括多个测试案例。T(T ≤ 20)，输入文件的第一行表示文件中有多少个测试案例。N(1 ≤ N ≤ 500)，每个测试案例的第一行表示会议室的数目。每个测试案例中，除第一行以外表示各个会议室的信息。每行会有3个数字，分别表示会议编号、会议起始时间、会议结束时间。[Output]输出可以安排的最大会议数目[I/O Example]Input261 1 102 5 63 13 154 14 175 8 146 3 12151 4 82 2 53 2 64 4 65 2 36 1 67 4 78 3 59 3 810 1 211 1 712 2 413 5 614 4 515 7 8Output35
练习模板
#include <cstdio> #include <iostream> using namespace std; int main( int argc, char** argv) { int tc, T; cin >> T; for(tc = 0; tc < T; tc++) { // TO DO here } return 0; // Your program should return 0 on normal termination. }
代码实现
题目中要求会议时间不可以冲突，所以可以利用贪心算法，尽可能的选择会议时间结束较早的会议室，这样就能安排最多的会议室。
#include <cstdio> #include <iostream> #include <vector> #include <algorithm> using namespace std; class MeetingRoom { public: int index; int start; int end; public: MeetingRoom( int i, int s, int e) : index(i), start(s), end(e) {} }; bool isEndEarly( const MeetingRoom r1, const MeetingRoom r2) { return (r1.end < r2.end); } int main( int argc, char** argv) { int tc, T; int num = 0; int count = 0; int index = 0; int start = 0; int end = 0; vector<MeetingRoom> rooms; freopen( " input.txt ", " r ", stdin); cin >> T; for(tc = 0; tc < T; tc++) { rooms.clear(); // clear vector // get all the info of rooms cin >> num; for ( int i = 0; i < num; i++) { cin >> index >> start >> end; MeetingRoom room(index, start, end); rooms.push_back(room); } // sort rooms for end time sort(rooms.begin(), rooms.end(), isEndEarly); // use greedy algorithm to solve promblem count = 1; MeetingRoom prev = rooms[ 0]; for (vector<MeetingRoom>::iterator it = rooms.begin() + 1; it != rooms.end(); it++) { MeetingRoom current = *it; if (current.start >= prev.end) { count++; prev = current; } } cout << count << endl; } return 0; }
