文章目录
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：区间合并，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上
一、关于区间合并
区间合并是一类贪心问题本博客所有例题，模板来自：AcWing，解本题用到了STL中的vector，有关vector，详见：STL—vector
二、例题与模板
1.AcWing 803. 区间合并
本题链接：AcWing 803. 区间合并
本博客给出本题截图：
本题分析
本题最重要和难理解的代码就是如下这一段，这里做出说明：
思路：把所有的区间按照左端点从小到大排序，然后从第一个区间开始遍历，如果后一个区间的左端点大于本区间的右端点，证明这两个区间没有交集，如图所示：
在这种情况下，就证明没有区间再可以和第一段区间进行合并了（因为我们已经按左端点进行排序），这样我们就把这个区间加入到res中，然后更新st和ed成下一个区间，最后res的长度就是一共有多少个区间，这里还需要注意一点：就是我们在把区间插入到res中时，插入的是上一个区间，这意味着我们最后会少插入一个区间，即最后一个区间，所以在遍历后，我们再把最后一个区间插入res就可以了
关于sort排序，按照first排序，first一样的话按照second排序，sort函数具体说明和应用详见：STL—algorithm（2）
void merge (vector<PII> &vi) { sort (vi.begin(), vi.end()); //按照左端点从小到大排序 int st = -2e9, ed = -2e9; //初始化左端点st和右端点为负无穷 //因为本题 l 和 r的范围是[-1e9, 1e9]所以我们初始化st和ed为 -2e9即可 for (auto it : vi) if (ed < it.first) //如果不满足区间合并的条件 { if (ed != -2e9) res.push_back({st, ed}); //因为我们初始的ed是-2e9，且这不是一个真正的区间所以我们要判断一下，如果不是我们初始化的那个区间[-2e9, 2e9]，就把这个区间插入res st = it.first, ed = it.second; //更新 st 和 ed } else ed = max (ed, it.second); //证明区间合并了，那么ed就取合并的两个区间中ed最大的那个作为新区间的ed res.push_back({st, ed}); //因为本题的 n≥1，所以肯定会保证必然有一个区间，故加入最后一个区间到res中 }
AC代码
#include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef pair <int, int> PII; vector <PII> res, v; void merge (vector<PII> &vi) { sort (vi.begin(), vi.end()); int st = -2e9, ed = -2e9; for (auto it : vi) if (ed < it.first) { if (ed != -2e9) res.push_back({st, ed}); st = it.first, ed = it.second; } else ed = max (ed, it.second); res.push_back({st, ed}); } int main() { int n; scanf("%d", &n); while (n -- ) { int st, ed; scanf("%d%d", &st, &ed); v.push_back({st, ed}); } merge (v); printf("%d", res.size()); return 0; }
2.模板
模板来自：ACWing算法基础课
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}); //这里的if就是判断是不是一组st和ed都没有输入进来 //在例题中因为保证n是≥1的，所以肯定不可能为空，就可以省去这一特判. segs = res; }
三、时间复杂度
关于区间合并的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
