首页 > 代码库 > 51Nod 1428 活动安排问题
51Nod 1428 活动安排问题
51Nod 1428 活动安排问题
Link： http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428
1428 活动安排问题
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题
Input
第一行一个正整数n (n <= 10000)代表活动的个数。 第二行到第(n + 1)行包含n个开始时间和结束时间。 开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000
Output
一行包含一个整数表示最少教室的个数。
Input示例
3 1 2 3 4 2 9
Output示例
2
题解：
简单的题目， 排序之后， 放进优先队列中，进行模拟，解决！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100000 + 5;
struct Node{
int r, l;
}nd[maxn];
int n;
int cmp(const void *a, const void *b){
Node *aa = (Node *)a;
Node *bb = (Node *)b;
return aa->l - bb->l;
}
int main(){
/// freopen("in.txt", "r", stdin);
int x, y, p, ans, cur;
while(scanf("%d", &n) != EOF){
for(int i=0; i<n; ++i){
scanf("%d %d", &nd[i].l, &nd[i].r);
}
qsort(nd, n, sizeof(nd[0]), cmp);
ans = 1;
priority_queue<int, vector<int>, greater<int>> qt;
qt.push(nd[0].r);
for(int i=1; i<n; ++i){
if(!qt.empty()){
cur = qt.top();
if(nd[i].l >= cur){
qt.pop();
}else{
++ans;
}
qt.push(nd[i].r);
}else{
qt.push(nd[i].r);
}
}
printf("%d\n", ans);
}
return 0;
}
51Nod 1428 活动安排问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。