区间分组
题目 区间分组
思路分析
数轴上有一些区间，要求将区间分成若干集合，每个集合中的区间两两不重叠。问：最少需要多少个这样的集合。
将区间按左端点排序。
依次遍历区间，如果当前区间能放到之前的某个集合中，则把该区间放到该集合，如果当前不能放到任意一个之前的集合中，则新开一个集合，把当前区间放到新开的集合中。
集合的数量就是答案。
关键步骤是第二步，如何判断当前区间能否放到之前的集合中。
解决方法如下:
记录每个集合中保存的区间的最右侧端点，如果当前区间的左端点不和某个集合中保存的区间的最右侧端点相交，则当前区间不和该集合相交，能放到该集合中。
也就是，我们只需判断当前区间的左端点 是否和 右侧端点最小的那个集合是否相交即可。
为了快速找出右侧端点最小的那个集合，可以使用小根堆保存每个集合的右端点。
证明：
设最优解为 ans, 算法解为 cnt
我们的方法找到的集合，各个集合中的区间，两两肯定不相交，因此 cnt >= ans
按照该算法，各个集合中的最后一个区间一定是两两相交的。如果存在不相交的区间，则这两个区间会被放到同一个集合中。
集合的数量，一定是当遍历到某个区间的时候，不能把当前区间放到任意一个集合中，导致了集合数量由cnt - 1 变为 cnt。也就是当前区间一定各个集合的最后一个区间有重叠部分。
综合2 3， 各个集合的最后一个区间两两相交，当前遍历到的区间和各个集合的最后一个区间都相交，因此，当前遍历的区间以及各个集合的最后一个区间两两相交。对于集合数量由cnt
- 1 变为 cnt 的时候，一定有 cnt 个区间两两相交。
为了将这cnt个区间互不相交，至少需要cnt 个集合，因此 cnt <= ans
有 1 得出cnt >= ans，由 5 得出 cnt <= ans， 所以cnt == ans。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
struct Range{
int l,r;
bool operator<(const Range& other)const{
return l<other.l;
}
}ranges[N];
priority_queue<int,vector<int>,greater<int>> ans;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>ranges[i].l>>ranges[i].r;
sort(ranges,ranges+n);
for(int i=0;i<n;i++){
if(ans.empty() || ranges[i].l<=ans.top())
ans.push(ranges[i].r);
else{
ans.pop();
ans.push(ranges[i].r);
}
}
cout<<ans.size();
return 0;
}
💬 评论