AcWing 906. 区间分组
原题链接
简单
作者:
less
,
2024-05-01 20:58:25
,
所有人可见
,
阅读 2
按左右端点排序都行,思想都是一样的
左端点
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;//左,右
#define N 100010
PII a[N];
int main()
{
int i,n;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i].first>>a[i].second;
sort(a,a+n);
priority_queue<int,vector<int>,greater<int>> q;//用来存每个组中右端点的最大值max_r,小根堆,所以q.top()取出来的是最小的max_r
for(i=0;i<n;i++)
{
if(q.empty()||q.top()>=a[i].first)//如果队列里没有元素,或者最小的max_r(右端点)都大于等于该区间的左端点(说明该区间的左端点与已知的所有区间都有交集),则需要开一个新的组存
q.push(a[i].second);
else//否则,把这个max_r改成该区间的右端点
{
q.pop();
q.push(a[i].second);
}
}
cout<<q.size()<<endl;
}
右端点
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;//右,左
#define N 100010
PII a[N];
int main()
{
int i,n;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i].second>>a[i].first;
sort(a,a+n);
priority_queue<int> q;//用来存每个组中左端点的最小值min_l,大根堆,所以q.top()取出来的是最大的min_l
for(i=n-1;i>=0;i--)//如果队列里没有元素,或者最大的min_l(左端点)都小于等于该区间的右端点(说明该区间的右端点与已知的所有区间都有交集),则需要开一个新的组存
{
if(q.empty()||q.top()<=a[i].first)
q.push(a[i].second);
else//否则,把这个min_l改成该区间的左端点
{
q.pop();
q.push(a[i].second);
}
}
cout<<q.size()<<endl;
}