区间和并

题目

给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3]和[2,6]可以合并为一个区间[1,6]。

输入格式
第一行包含整数n。接下来n行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围
1≤n≤100000,−109≤li≤ri≤109

输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3

分析

这个题的题意是给出 n 个区间的左端点和右端点，如果两个区间有交集的话就将他们合并为一个区间，问最后还有几个区间。

首先读入所有的区间，然后将所有的区间先按照左端点排序然后再按照右端点排序，如果一个区间的左端点小于前一个区间的右端点，然后在比较前一个区间的右端点和这个区间的右端点谁的大然后就将右端点更新为较大的

代码

#include<iostream>
#include<algorithm>
using namespace std;

int a[123456];
struct node{
    int l,r;
}aa[123456];
bool cmp(node a,node b)
{  //排序
    if(a.l==b.l) return a.r<b.r;
    return a.l<b.l;
}

int main()
{
    int n,k=1;
    cin>>n;
    for(int i=0;i<n;i++) cin>>aa[i].l>>aa[i].r;
    sort(aa,aa+n,cmp);
    a[k]=aa[0].r;  //初始化为第一个区间的右端点
    for(int i=1;i<n;i++)
    { 
        if(aa[i].l<=a[k]) a[k]=max(a[k],aa[i].r);
        else a[++k]=aa[i].r;  //这个区间的左端点不小于上一个区间的右端点
    }
    cout<<k<<endl;
    return 0;
}