实在受不了数论的折磨于是感觉贪心友好多了but不严谨证明多少带点运气成分((
题目:
给定 N 个闭区间 [ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示最小组数。
数据范围
1≤N≤1e5,
−1e9≤ai≤bi≤1e9
输入样例:
3
-1 1
2 4
3 5
输出样例:
2
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100010;
struct Range {
int l, r;
bool operator< (const Range& w)const {
return l < w.l;
}
};
Range range[N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
range[i] = { l,r };
}
priority_queue<int, vector<int>, greater<int>>heap;
sort(range, range + n);
for (int i = 0; i < n; i++) {
if (heap.empty() || heap.top() >= range[i].l) {
//如果当前空或者最右端严格>=最左端
heap.push(range[i].r);//那就要新加一个组
}
else {
heap.pop();
heap.push(range[i].r);
}
}
cout << heap.size();
return 0;
}