首页 > 代码库 > 51Nod 1428 活动安排问题

51Nod 1428 活动安排问题

 

51Nod   1428  活动安排问题

Link: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428

 

1428 活动安排问题
基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题
技术分享有若干个活动,第i个开始时间和结束时间是[Si,fi),同一个教室安排的活动之间不能交叠,求要安排所有活动,最少需要几个教室? 
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 活动安排问题