算法基础：区间合并算法及模板应用

2022-11-23
山东
本文字数：1125 字
阅读完需：约 4 分钟

区间合并

⭐写在前面的话：本系列文章旨在复习算法刷题中常用的基础算法与数据结构，配以详细的图例解释，总结相应的代码模板，同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的 C++基础的学习者。若 C++基础不牢固，可参考：10min快速回顾C++语法，进行语法复习。
🔥本文已收录于算法基础系列专栏：算法基础教程免费订阅，持续更新。

基本思想

将多个区间进行合并，其中有交集的区间合为一个区间，没有交集的区间保留原状。注意，这里端点重合也算作一种交集区间。

算法的图解如下：

算法思路

首先按照区间的左端点进行排序。

然后维护一个最左侧的区间。设头节点为 st，尾节点尾 ed。

可能会有以下三种情况：

1.下一个区间在本区间中。

则将区间更新为两个区间的并集，将尾节点设置为两区间最大的节点即可。

2.下一个区间有交集

3.下一个区间没有交集

将该区间放到 result 中，并且将区间 st，ed 移动至下一个区间（维护的区间更新为下一个区间）。

例题：区间合并

给定 n 个区间 [ $l_{i}, r_{i}$ ]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

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

数据范围

1≤n≤100000 $- 1 0^{9}$ ≤ $l_{i}$ ≤ $r_{i}$ ≤ $1 0^{9}$

输入样例：

51 22 45 67 87 9

复制代码

输出样例：

复制代码

code

#include<iostream>#include<algorithm>#include<vector>
using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;
void merge(vector<PII> &segs){    vector<PII> res;    // 默认先对左端点（第一个变量）进行排序    sort(segs.begin(), segs.end());    // 定义在参数区间的最左端    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;    cin >> n;    while(n --)    {        int l, r;        cin >> l >> r;        // 保存参数        segs.push_back({l, r});    }    // 合并    merge(segs);    // 返回个数即可    cout << segs.size() << endl;    return 0;    }

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/b0d0d9e30a6ca8b71fe0359d0】。未经作者许可，禁止转载。

timerring

关注

还未添加个人签名 2022-07-14 加入

还未添加个人简介

发布

暂无评论

创作场景

算法基础：区间合并算法及模板应用

区间合并

基本思想

算法思路

例题：区间合并

code

timerring

评论