题目描述
[题目描述] 在大公司里,会议是很多的,开会得有场子,要场子你得先在电子流里预订。 |
练习模板
#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 <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;
}
#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;
}