区间合并
合并有交集的区间(含端点相交).
样例
输入样例:
5
1 2
2 4
5 6
7 8
7 9
输出样例:
3
合并区间
解题思路
1.将区间按左端点从左到右排序.
2.维护一个待合并区间[st,ed],从左到右扫描排好序的区间:
若扫描的当前区间与待合并区间有交集,合并两个区间,更新待合并区间右端点;
若无交集,将待合并区间更新为当前扫描区间.
时间复杂度
O(n)
C++ 代码
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
int n;
vector<pii> segs;
void merge(vector<pii> &segs)
{
if( segs.size()==0 )
return;
sort(segs.begin(),segs.end()); //先排序
vector<pii> res;//暂时存储合并后的区间
int st = segs[0].first, ed = segs[0].second;
for( int i = 1; i<segs.size(); i++ )
{
if( segs[i].first<=ed )
{//当前扫描区间与待合并区间[st,ed]有交集
ed = max( ed, segs[i].second );
}
else
{//无交集
res.push_back({st,ed});
st = segs[i].first, ed = segs[i].second;
}
}
res.push_back({st,ed}); //最后一个区间因为扫描完而退出 没有经过if else判断
segs = res;
}
int main()
{
cin >> n;
for( int i = 0; i<n; i++ )
{
int l, r;
cin >> l >> r;
segs.push_back({l,r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}