我要评论又到毕业季，很多大公司来学校招聘，招聘会分散在不同时间段，小明想知道自己最多能完整的参加多少个招聘会(参加一个招聘会的时候不能中断或离开)。
思路
算法导论贪心算法章节原题, 编程之美上也有类似题目.
这种招聘会还比较简单, 招聘会本身没有权值, 假如考虑权值, 题目就变成动态规划了
先对招聘会按照截止时间排序, 然后按照截止时间选取具体哪场招聘会, 时间复杂度为 o(nlogn)
代码
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
class meeting {
public:
int st, ed;
meeting(int _st, int _ed):st(_st), ed(_ed) {
}
meeting() {
meeting(0, 0);
}
bool operator<(const meeting &ths) const{
if(this->ed != ths.ed)
return this->ed < ths.ed;
return this->st < ths.st;
}
};
int main() {
int n;
while(scanf("%d", &n) != eof) {
vector<meeting> meetings;
for(int i = 0; i < n; i ++) {
int st, ed;
scanf("%d%d", &st, &ed);
meetings.push_back(meeting(st, ed));
}
sort(meetings.begin(), meetings.end());
int res = 0;
int lastpos = 0;
for(int i = 0; i < meetings.size(); i ++) {
if(meetings[i].st >= lastpos) {
res ++;
lastpos = meetings[i].ed;
}
}
printf("%d\n", res);
}
return 0;
}
发表评论