一、区间合并
- 区间合并，是指将若干个 有交集 的区间合并为 1 个区间。关于区间的写法，我们可以用结构体进行实现，其中既包括左节点，也包括右节点。
struct Interval { int left； int right; };
- 区间合并本身并不复杂，也好理解，因此在此不过多叙述了。
二、区间合并例题——区间和并
题目描述
给定 n 个区间 [li , ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1 ≤ n ≤ 100000 ,
−1e9 ≤ li ≤ ri ≤ 1e9
输入样例
5
1 2
2 4
5 6
7 8
7 9
输出样例
3
具体实现
1. 样例演示
2. 实现思路
- （1） 按区间的左端点进行排序。
- （2） 扫描每个区间，将每个可能有交集的区间进行合并。有如下图三种可能：
| 颜色 | 情况 | 更新方法 |
| 绿色 | 包含 | 原区间端点不变 |
| 黄色 | 相交 | 左端点不变，右端点延长 |
| 粉色 | 没有交集 | 从当前区间开始，后面的所有区间与原区间没有交集，便可将原区间放入答案当中，左右端点更新为粉色区间 |
3. 代码注解
if (st != -2e9) res.push_back({st, ed}); 的作用：是防止n为0，把 [-无穷，-无穷] 压入和压入最后一个（也就是当前）的区间，若 n>=1，if 可以不要。
4. 实现代码
#include <bits/stdc++.h> 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; cin>>n; vector<PII> segs; for (int i = 0; i < n; i ++ ) { int l, r; cin>>l>>r; segs.push_back({l, r}); } merge(segs); cout << segs.size() << endl; system("pause"); return 0; }
