算法学习系列（十二）：区间合并

引言

这个区间合并顾名思义就是把区间给合并起来，所以说也就只有这一种题型，然后这个一般面试或者笔试可能会考，所以说总结一下还是好的，那就开始吧。

一、题目描述

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

二、解题思路

首先我们的这个区间必须是以左端点由大到小排好序的，然后在进行处理。
其实这个区间合并无非就两种情况，如下图所示，
第一种情况：下一个区间的左端点比上一个区间的右端点小，那就将 r = max(r, new_r)，找到这两个区间右端点最大的一个更新区间
第二种情况：下一个区间的左端点比上一个区间的右端点大，那么上一个区间就可以加入到结果集中了，然后更新目前的区间的左右端点

在这里插入图片描述

三、代码实现

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> PII;
#define x first
#define y second

int n;

void merge(vector<PII>& segs)
{
    vector<PII> res;
    sort(segs.begin(), segs.end());
    
    int l = -2e9, r = -2e9;
    for(int i = 0; i < segs.size(); ++i)
    {
        if(segs[i].x > r)
        {
            if(r != -2e9) res.push_back({l,r});
            l = segs[i].x, r = segs[i].y;
        }
        else
        {
            r = max(r, segs[i].y);
        }
    }
    
    if(r != -2e9) res.push_back({l,r});  //最后一个区间因为没人比了，所以要加进来，当然如果初始区间为空就不行了
    
    segs = res;  //最后将结果集拷贝给segs，通过引用传出去
}

int main()
{
    scanf("%d", &n);
    vector<PII> segs;
    for(int i = 0; i < n; ++i)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        segs.push_back({l,r});
    }
    
    merge(segs);
    
    printf("%d\n", segs.size());
    
    return 0;
}