AcWing 906. 区间分组
原题链接
简单
作者:
我要出去乱说
,
2021-01-31 14:22:27
,
所有人可见
,
阅读 252
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n;
struct Range
{
int l, r;
bool operator< (const Range& t) const
{
return l < t.l;
}
}range[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
int l, r;
cin >> l >> r;
range[i] = {l, r};
}
sort(range, range + n); //区间按照左端点排序
priority_queue<int, vector<int>, greater<int>> heap; //建立小根堆,heap.top()元素为最小元素
for (int i = 0; i < n; i ++ ) //遍历区间
{
auto r = range[i];
if (heap.empty() || heap.top() >= r.l) heap.push(r.r); //堆为空或当前区间与前区间有交集,堆元素加1
else //当前区间与前区间无交集,则将前区间右端点替换为当前区间右端点,小根堆会自动排序
{
heap.pop();
heap.push(r.r);
}
}
cout << heap.size() << endl; //堆的size即分组个数
return 0;
}