题目描述

给定 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

算法1

感悟

C++ 代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;//这里也用到pair函数,因为这里也用到了一些离散化
vector<PII> a;
void merge(vector<PII> &a){
    vector <PII> c;
    int st=-2e9,ed=-2e9;//
    for(auto item:a)//自动遍历，第一个为变量，第二个为遍历数组
    {
        if(item.first>ed)
        //这有两层含义，当第一次时对st和ed赋值，第二种是在无合并下对当前区间录入
        {
            if(ed!=-2e9) c.push_back({st,ed});
            st=item.first;ed=item.second;
        }
        else 
        ed=max(ed,item.second);//选取最大值，对区间进行合并
    }
    if(ed!=-2e9) c.push_back({st,ed});
    //这一步非常重要，我老忘，判断是避免这里是空数组，这是加入剩余的数组，
    //因为最后一个没有元素，也就不会有item.first>ed
    a=c;//将c赋值于a
}
int main()
{
    int n;
    cin>>n;
    while(n--){
        int l,r;
        scanf("%d %d",&l,&r);
        a.push_back({l,r});
    }
    sort(a.begin(),a.end());//pair函数主观上排序第一个数据即a.first
    merge(a);
    cout<<a.size()<<endl;//由数据个数表示区间个数

}