首页 > 代码库 > 51nod1428(优先队列)
51nod1428(优先队列)
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428
题意:中文题诶~
思路:贪心
问最少要多少教室就是求最多有多少个时间段产生了交集咯。我们先用结构体存储区间并将其按照左端点升序排列,若左端点相同则按右端点升序排列。
接下来遍历所有区间,并维护一个优先队列,其中存储区间右端点值。对于当前区间,我们将优先队列中所有比当前区间左端点小的元素删除(因为其所在区间不会与当前区间相交嘛),然后再将当前区间的右端点加入优先队列。当前优先队列的大小就是当前能得到的最大交集数。其中道理并不复杂就不多说啦。。。
代码:
1 #include <bits/stdc++.h>
2 #define MAXN 10010
3 using namespace std;
4
5 struct Node{
6 int l, r;
7 }gg[MAXN];
8
9 int cmp(Node a, Node b){
10 return a.l==b.l?a.r<b.r:a.l<b.l;
11 }
12
13 int main(void){
14 int n, ans=0;
15 cin >> n;
16 for(int i=0; i<n; i++){
17 cin >> gg[i].l >> gg[i].r;
18 }
19 sort(gg, gg+n, cmp);
20 priority_queue<int, vector<int>, greater<int> > q;
21 for(int i=0; i<n; i++){
22 while(!q.empty()){
23 int a=q.top();
24 if(a<=gg[i].l){
25 q.pop();
26 }else{
27 break;
28 }
29 }
30 q.push(gg[i].r);
31 int cnt=q.size();
32 ans=max(ans, cnt);
33 }
34 cout << ans << endl;
35 return 0;
36 }
51nod1428(优先队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。