题目描述

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

代码&思路

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
vector<PII> res; 
void memerg(vector<PII> &res)
{
    vector<PII> num;
    sort(res.begin(),res.end());//排序的时候先排左端点
    int st=-2e9,ed=-2e9;
    for(auto seg:res)
    {
        if(ed<seg.first)//判断两个区间是不是没有交集
        {
            if(st!=-2e9)
            {
                num.push_back({st,ed});
            }
            st=seg.first,ed=seg.second;
        }
        else//如果有交集
        {
            ed=max(ed,seg.second);
            //排序是从左端点开始排的，左端点只能相等或者在上一次的右边，直接取上一次的即可
            //右端点要取比较靠右的那个，做到合并
        }
    }
    if(st!=-2e9) num.push_back({st,ed});//当没有元素的时候就不存入
    res=num;
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int l,r;
        cin >> l >> r;
        res.push_back({l,r});
    }
    memerg(res);
    cout << res.size();
    return 0;
}