AcWing 906. 区间分组
原题链接
简单
作者:
Nevdie_
,
2021-03-20 13:28:21
,
所有人可见
,
阅读 261
#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n;
PII a[N];
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d%d", &a[i].x, &a[i].y);
sort(a, a + n);
priority_queue<int, vector<int>, greater<int> > heap; //维护所有已建组的右端点
heap.push(a[0].y); //将第一个区间新建为第一个组
for(int i = 1; i < n; i++)
{
if(a[i].x <= heap.top()) heap.push(a[i].y); //新建一个组
else heap.pop(), heap.push(a[i].y); //加入堆顶的组
}
printf("%d", heap.size());
return 0;
}