区间合并

⬅ 返回

1、思路

先按左端点排序，再维护一个区间，右端点记为rt，与后面一个个区间进行两种情况的比较，存储到数组里去。

若当前遍历区间v[i]的左端点小于等于当前维护区间的右端点，区间合并，rt=max(rt,v[i].second);

若当前遍历区间v[i]的左端点大于当前维护区间的右端点，维护一个新区间，rt=v[i].second;sum++;

2、例题

3、代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> PII;
vector<PII> v;
 
int main(){
	int n;cin>>n;
	for(int i=0;i<n;i++)
	{
		int l,r;
		cin>>l>>r;
		v.push_back({l,r});
	} 
	-----------------------------------------------------------------------
	sort(v.begin(),v.end());//1、按照左端点排序
	int sum=1;//2、记录区间数量 直接拿第一个区间开始维护
	int rt=v[0].second;//3、rt维护当前区间的有边界
	
	for(int i=1;i<n;i++)//4、从第二个区间开始遍历
	{
		if(v[i].first<=rt)//5、如果当前区间的左端点<=维护区间的右端点
		{
			rt=max(rt,v[i].second);//区间合并
		}
		else{
			sum++;//维护新区间
			rt=v[i].second;//新区间右边界
		}
	}
	cout<<sum<<endl;
}