题目描述

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

set集合排序 + 我也不知道是什么算法

先写个struct二元组，然后利用set的性质排序，具体见代码的注释....

C++ 代码

#include<bits/stdc++.h>
using namespace std;

//#define N 100010

int n;

struct XX{
    int x,y;

    bool operator < (const XX &a) const { //重载小于号，按x从小到大排，x相同，则按y从小到大
        if(a.x != x){
            return x < a.x;
        }
        else return y < a.y;
    }
};

int main(){
    cin >> n;

    set<XX>s;

    int k1 = n;

    while(k1 --){
        int l,r;

        scanf("%d %d", &l , &r);

        s.insert({l,r});
    }

    int k2 = n;

    set<XX>::iterator it = s.begin();//迭代器遍历set集合

    n --;//由于第一次的l，r先赋值了，所以相当于让下面的while少一层循环

    int l = it->x, r = it->y, roundl = it->x, roundr = it->y;//l，r表示当前的it->x和it->y的值，roundl和roundr表示左右边界的值

    it++;//指向set的下个二元组

    while(n --){
        l = it->x;

        if(l <= roundr) {
            k2--;

        } else { // 如果出现了更大的区间（即新出现的区间左端点，在当前区间的右端点的右边），则更新边界
            roundl = it->x;

            roundr = it->y;
        }

        if(it->y > roundr) roundr = it->y;//防止没出现更大区间的情况下，出现it->y的值比右边界大的情况，则需要扩展区间

        //r = it->y;

        it++;
    }

    //for(it = s.begin(); it != s.end(); it++)cout << it->x << " " << it->y << endl;

    cout << k2 << endl;

    return 0;
}