区间合并笔记

文章目录 什么是区间合并怎么做区间合并AcWing 803. 区间合并思路解析my - CODEdalao の CODE

---

---

什么是区间合并

区间合并是指给定多个区间，让你将重合的区间合并为一个区间

---

怎么做区间合并

区间合并类问题大多三个办法：

按左端点排序按右端点排序按左右端点双值排序

---

AcWing 803. 区间合并

题目链接： .acwing /activity/content/problem/content/837/

思路解析 我们按左端点大小将区间排序，排完序后从每个区间左端点开始遍历，我们会发现有三种情况 B区间在A内C区间有一部分与A重合D区间在A外 我们的思路很明了了，通过两个指针：st(start)，ed(end) 来标记我们正在维护的A数组的左右端点，往后遍历，处理三种情况 如果遇到B：左端点不动，右端点也不动如果遇到C：左端点不动，右端点更新为C的右端点，也就是将A,C区间合并了如果遇到D：左右端点更新为D的左右端点，相当于现在改为维护D区间 my - CODE #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef pair<int, int> pii; vector<pii> segs; // 存储区间左右端点 int main() { int n, l, r; int ans = 0; cin >> n; while (n -- ){ scanf("%d%d", &l, &r); segs.push_back({l, r}); } sort(segs.begin(), segs.end()); // 以左端点优先排序 int st = -1e9 - 1, ed = -1e9 - 1; // 一开始的区间初始化为一个不可能的区间 for(auto seg : segs){ if(seg.first <= ed) ed = max(ed, seg.second); // 有重合，右端点取最大 else{ // 无重合，更新维护的区间 ans++; st = seg.first; ed = seg.second; } } cout << ans << endl; } dalao の CODE #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; 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; 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); cout << segs.size() << endl; return 0; } 作者：yxc 链接： .acwing /activity/content/code/content/40108/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 dalao将合并统计区间的过程抽出来单独写了个merge()函数，复用性和可读性更强而且将合并后的区间按秩存入了一个res空间，对于本题可能没有卵用，但是在其他区间合并问题中可能会用到合并后的区间不愧是dalao啊，orz %%%%%%