题目描述
给定 n个区间 [li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3]和 [2,6]可以合并为一个区间 [1,6]。
样例
输入样例
5
1 2
2 4
5 6
7 8
7 9
输出样例
3
思路提示
不需要设置边界的位置来合并区间
1.根据左端点进行排序
2.设初始区间数为1
3.比较第一个区间的右端点和第二个区间的左端的,如果可以合并,则更新第二个区间的右端点为远的端点;不能合并,则区间数+1
4.在合并过程中注意边界
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
typedef pair<int,int> PII;
vector<PII> a;
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d %d",&l,&r);
a.push_back({l,r});
}
int res=1;
sort(a.begin(),a.end());
for(int i=0;i<n;i++)
{
if(a[i].second<a[i+1].first&&i+1<n) //注意边界:i+1<n
{
res++;
}
else
{
a[i+1].second=max(a[i].second,a[i+1].second); //重点,更新区间的右端点
}
}
cout<<res<<endl;
return 0;
}