题目描述
给定 N 个闭区间 [ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。
样例
输入样例:
3
-1 1
2 4
3 5
输出样例:
2
贪心算法
- 所有区间按左端从小到大排序
- 枚举所有区间
判断是否能加入任意一个已确定的区间
若rang[i].l<max_r
,则加入所有max_r最小的区间
若rang[i].l>=max_r
,则新建一个区间
max_r
表示一个已经确定的区间右端点的最大值
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010;
struct Rang
{
int l,r;
bool operator<(Rang &w)
{
return l<w.l;
}
}rang[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d%d",&l,&r);
rang[i]={l,r};
}
sort(rang,rang+n);
priority_queue<int,vector<int>,greater<int>> heap;//小根堆
for(int i=0;i<n;i++)
{
Rang t=rang[i];
if(heap.empty()||heap.top()>=t.l)heap.push(t.r);
else
{
heap.pop();
heap.push(t.r);
}
}
cout<<heap.size()<<endl;
return 0;
}