区间合并

1.基本思想

问题描述
输入一个区间的合集，将有重叠的区间合并成一个新的区间（本题中后一个区间的起点和前一个区间的终点重合，也算两个区间重叠，需要合并）

算法思想
先按左端点排序，再维护一个区间，与后面一个个区间进行三种情况（见下图）的比较，存储到数组/向量中

2.参考题目与代码实现（`AcWing` 803.区间合并）

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

输入格式
第一行包含整数n。接下来n行，每行包含两个整数l和r。

输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围
$$
1 \le n \le 1e5\
-10^9 \le l_i \le r_i \le 10^9
$$
样例
输入样例：
5
1 2
2 4
5 6
7 8
7 9
输出样例：
3

代码实现

#include 
#include 
#include 
using namespace std;
typedef pair PII;

void merge(vector &segs) {
    vector res;

    sort(segs.begin(), segs.end());//根据左端点从小到大进行排序
    /*sort函数对pair进行排序，默认情况下，先对first进行从小到大排序，fitst相同再根据second从小到大进行排序*/

    int st = -2e9, ed = -2e9;//维护区间初始化
    for (auto seg : segs)
        if (ed < seg.first)//如果下一个区间的起点在当前维护区间外面（右端点的右侧）
        {
            if (st != -2e9) res.push_back({st, ed});//存储原维护区间
            st = seg.first, ed = seg.second;//新的维护区间建立
        }
        else ed = max(ed, seg.second);//否则，则合并

    if (st != -2e9) res.push_back({st, ed});//存储最后一个维护区间

    segs = res;
}

int main() {
    int n;
    scanf("%d", &n);

    vector segs;
    for (int i = 0; i < n; i ++ ) {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l, r});
    }//输入与存储

    merge(segs);//区间合并主过程
    
    cout << segs.size() << endl;
    return 0;
}