[AcWing]803. 区间合并（C++实现）区间合并模板题

[AcWing]803. 区间合并（C++实现）区间合并模板题

[AcWing]803. 区间合并（C++实现）区间合并模板题

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

初步思路：

------------------------------------------------------代码实现思路-----------------------------------------------------------

1. 读取各个区间存放在segs中；
2. 对segs排序，合并区间，将合并的区间存放在res中；
3. 返回res.size()得到合并后的区间数。

合并区间模板
① 输入的区间在维护的区间内；ed = ed;
② 输入的区间和维护的区间有交集； ed = seg.second;
综合①②得到 ed = max(ed,seg.second);

③ 完全没有交集，将当前维护的区间添加到res中，然后取下一个区间进行维护。

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include
#include
#include
using namespace std;

typedef pair PII;
vector res,segs; // segs用于存放原区间，res存放合并后的区间
int n;

vector merge(vector &segs){
    sort(segs.begin(),segs.end());
    int st = -2e9, ed = -2e9;
    for(auto seg : segs){
        if(seg.first > ed){
            if(st != -2e9) res.push_back({st,ed});
            st = seg.first;
            ed = seg.second;
        }else ed = max(seg.second,ed);
    }
    // 最后一个区间
    if(st != -2e9) res.push_back({st,ed});
    return res;
}

int main(){
    cin >> n;
    for(int i = 0;i < n;i++){
        int l,r;
        cin >> l >> r;
        segs.push_back({l,r});
    }
    merge(segs);
    cout << res.size() << endl;
    return 0;
}

4. 可能有帮助的前置习题

• [AcWing]789. 数的范围（C++实现）整数二分模板题
• [AcWing]795. 前缀和（C++实现）一维前缀和模板题

5. 所用到的数据结构与算法思想

• C++模板类型—pair
• C++数据结构—vector容器
• C++头文件—algorithm

6. 总结

本题使用了区间合并以及贪心的思想。
在数据结构方面使用了vector、pair等数据结构，是一道比较综合的区间合并模板题。
推荐完全背下来。