https://www.51nod.com/Challenge/Problem.html#!#problemId=1428
有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？
输入
第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000
输出
一行包含一个整数表示最少教室的个数。
输入样例
3
1 2
3 4
2 9
输出样例
2
如果要加入的活动开始时间小于已开始活动的最早结束时间，则新开一个教室
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <set>
#include <utility>
#include <vector>
#include <map>
#include <stack>
using namespace std;
#define MAX 10000+10
#define INF 0x3f3f3f3f
int n,ans;
pair<int,int> a[MAX];
priority_queue<int > p;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d %d",&a[i].first,&a[i].second);
}
sort(a,a+n);
for(int i=0;i<n;i++){
if(p.size()&&-p.top()<=a[i].first){
p.pop();
p.push(-a[i].second);
}else {
ans++;
p.push(-a[i].second);
}
}
printf("%d",ans);
return 0;
}
|