题目描述
算法1
不使用最小堆去维护
最开始想的时候,没又想到最小堆去维护maxr。
用的是一个数组去存贮各个分组的maxr
每次都必须遍历一遍这个数组,找到插入位置。
但是 因此会超时
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
PII p[N];
int maxr[N];
int maxgroups=0,idx=0;//idx用于标记到了第几个组
bool comp(PII a,PII b){
return a.first<b.first;
}
int main(){
int number;
scanf("%d",&number);
for(int i =0;i<number;i++){
scanf("%d%d",&p[i].first,&p[i].second);
}
sort(p,p+number,comp);
for(int i = 0;i<number;i++){
int flag = 0;
for(int j=0;j<idx;j++){
if(p[i].first>maxr[j]){
maxr[j] = p[i].second;
flag =1;
break;
}
}
if(flag == 0){
maxr[idx++] = p[i].second;
maxgroups++;
}
}
cout<<maxgroups<<endl;
}
算法2
最小堆维护
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 100010;
PII p[N];
bool comp(PII a,PII b){
return a.first<b.first;
}
int main(){
int n;
scanf("%d",&n);
for(int i =0;i<n;i++){
scanf("%d%d",&p[i].first,&p[i].second);
}
sort(p,p+n,comp);
priority_queue<int,vector<int>,greater<int> > heap;//定义最小堆去维护
for(int i = 0;i<n;i++){
auto r = p[i];
if (heap.empty() || heap.top() >= r.first) heap.push(r.second);
else
{
heap.pop();
heap.push(r.second);
}
}
cout<<heap.size()<<endl;
}