AcWing 906. 区间分组
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-20 10:45:52
,
所有人可见
,
阅读 176
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n;
struct Range {
int l, r;
bool operator< (const Range &W)const {
return l < W.l;
}
} Range[N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i ++) {
int l, r;
scanf("%d%d", &l, &r);
Range[i] = {l, r};
}
sort(Range, Range + n);
priority_queue<int, vector<int>, greater<int>> heap; //使用小根堆来进行维护
for (int i = 0; i < n; i ++) {
//首先来取出来每一个区间
auto t = Range[i];
int l = t.l;
//如果此时堆中为空, 此时肯定要来开辟一个新的组
if (heap.empty() || l <= heap.top()) heap.push(t.r);
else {
//如果此时可以放到其中的一个组中
//此时需要将堆给删掉, 因为此时的堆定不再是当前组中的最右的区间值了
heap.pop();
heap.push(t.r);
}
}
printf("%d", heap.size());
return 0;
}