为何必须按左端点排序呢?
因为当我们按照左端点进行排序时左端点是从小到大进行排序的,也就是对左端点进行一一枚举时,对于任意一个左端点大于分组内所存的最大值(也就是更新的右端点)左端点前面的点都用不到或者已经用上了不会存在跨度较大的浪费,而对右端点进行排序时,由于针对的是右端点,左端点会存在较大的跳节,列如一个组内左右端点本来是负数,而下一个所枚举的点的左端点是正数,虽然肯定大于这个组的右端点,并更新这个右端点,但是,一个负数区间直接跨越到一个正数区间而中间的全部都浪费掉了,所以所用到的分组必定增加!
题目描述
给定 N 个闭区间 [ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
输出格式
输出一个整数,表示最小组数。
数据范围
1≤N≤105,
−109≤ai≤bi≤109
样例
输入样例:
3
-1 1
2 4
3 5
输出样例:
2
算法
(贪心)
C++ 代码
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
struct ra{
int l,r;
bool operator <(const ra &w)const {
return l<w.l;
}
}re[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
re[i]={a,b};
}
sort(re+1,re+n+1);
priority_queue<int ,vector<int >,greater<int >>hp;
for(int i=1;i<=n;i++){
if(hp.empty()||re[i].l<=hp.top())
hp.push(re[i].r);
else {
hp.pop();
hp.push(re[i].r);
}
}
cout<<hp.size();
}
( 举一个不用右端点的反例:
[[1,3],[4,7],[1,4],[5,6]] )