思路
这个区间贪心问题,是要按照区间左端点排序。
和之前区间问题一样,我们需要分情况讨论贪心决策
1.如果一个区间的左端点比当前每一个组的最右端点都要小,那么意味着要开一个新区间了,这个条件还可以优化成,一个区间左端点比最小组的右端点都要小就开一个新组。
2.如果一个区间的左端点比最小组的右端点大,那么就放在该组,这其实也是一个贪心,因为是先考虑最容易放入一个区间的组嘛
这道题对于数据结构上的选择也要考虑,用一个小顶堆,也就是优先队列来存储每一个组的最右端点是最好的数据结构了。
步骤
1.按区间左端点排序
2.扫描所有区间,按以上情况分开处理
3.最后堆中存的所有数据的个数就是组的个数
代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e5+5;
struct Range{
int r,l;
bool operator < (const Range& w)const{
return (l<w.l)||(l==w.l&&r<w.r);
}
}ranges[N];
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++){
cin >> ranges[i].l >> ranges[i].r;
}
sort(ranges,ranges+n);
priority_queue<int, vector<int>, greater<int>> heap;
for(int i=0;i<n;i++){
if(heap.empty()||ranges[i].l<=heap.top())heap.push(ranges[i].r);
else{
heap.pop();
heap.push(ranges[i].r);
}
}
cout << heap.size();
}