[算法题] 安排会议室——贪心算法的应用
题目描述
[题目描述]
在大公司里，会议是很多的，开会得有场子，要场子你得先在电子流里预订。 如果你是项目组新来的小弟，那么恭喜你，每天抢订会议室的任务就光荣的分给你了。 老大要求你尽可能多的订会议室，但是这些会议室之间不能有时间冲突。 [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 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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-03-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读