AcWing 906. 区间分组
原题链接
简单
作者:
阿飞被注册了
,
2021-06-07 19:27:17
,
所有人可见
,
阅读 394
C++ 代码
// 优先队列--priority_queue: 默认大根堆。
// 大根堆定义: priority_queue<int, vector<int>, less<int>> s;
// 小根堆定义:priority_queue<int, vector<int>, greater<int>> s;
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5+10;
struct range{
int l, r;
bool operator < (const range &M)
{
return l < M.l;
}
}p[N];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
p[i] = {l, r};
}
sort(p, p+n);
priority_queue<int, vector<int>, greater<int>> qe;
for(int i = 0; i < n; i++)
{
auto x = p[i];
if(qe.empty() || qe.top() >= x.l) qe.push(x.r);
else
{
qe.pop();
qe.push(x.r);
}
}
cout << qe.size();
return 0;
}