AcWing笔记 -- 区间合并
前言
给定多个区间，如[1, 8] , [7 , 12] , [15, 18], [18 , 25]。可以看出，这些区间之间是有交集的，比如[1,8]和[7,12]以及[15,18]，[18,25]。这两对区间可以合并，变为[1, 12]以及[15 , 25]。区间合并解决的就是给定多个区间段，让我们判断哪些区间可以合并，最后给出独立区间段个数的问题。
实现
对于给定两两区间A，B之间，显然有三种情况。
1. B区间包含于A区间。
2. B区间与A区间有交集但不含于A区间。
3. B区间与A区间无交集。
三种情况的示意图如下
显然前两种情况是需要合并的，而第三种情况下，说明A区间与后面的区间不会再有交集了。因此A区间已经成为一个独立区间。
注意由于我们是从大到小依此扫描，不会出现B区间的头大于A区间的头的情况
我们以下面这道题为例，实现区间合并
给定 n个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3]和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−109≤li≤ri≤109
题解如下：
对于给出的每个区间，我们用pair型的vector来读入存储。而且存储之后排一下序。
sort对pair排序，会先以其first作为基准排序，再以其seconed作为基准排序。
排序之后我们便开始区间合并。合并操作都在merge函数中。
定义一个st以及ed，分别指向我们当前所维护的区间的头尾。为防止与输入冲突，初始化为负无穷。
然后去扫瞄读入的排好序的每个区间，并与维护区间进行上述三种情况的判断。
- 若维护区间与当前区间无交集，代表着当前区间的头大于维护区间的尾，也就是item.second > ed ，说明维护区间与后续区间再无交集，因此当前的维护区间已经成为一个独立区间，将其加入到答案数组中。同时更新当前维护区间为此时的item，即令st = item.first , ed = item.second。当然这里要特殊考虑第一次的情况，第一次更新时只更新维护区间而不将维护区间加入答案。
- 若维护区间与当前区间有交集(若1不成立即判断为有交集)，进行的为上述情况1，2。更新当前维护区间的尾，即让ed = max（ed，item.second）,这样包含了两种情况的更新
- 注意所有区间遍历完之后，一定会剩下一个维护区间为加入答案数组之中，所以循环退出之后要加上最后的维护区间。
最后代码如下
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int, int> PII;
vector<PII> ran;
void merge(vector<PII>& range)
{
vector<PII> ans;//答案
int st = -0x3f3f3f3f;
int ed = st;
//st以及ed为当前维护区间的区间头尾
//对于每个item，都为下一个将要判断的区间
for (auto item : range)//c++区间遍历
{
if (ed < item.first)//若没有交集，说明当前维护的区间与以后的区间再无并集，找到独立区间
{
if(ed!=-0x3f3f3f3f)//第一次的特殊情况。
ans.push_back({ st, ed });
st = item.first;
ed = item.second;//更新当前所要维护的区间
}
else//若有交集，合并
{
ed = max(ed, item.second);//考虑了item在所维护区间内部以及item与所维护区间有一部分交集两种情况
}
}
//显然对于最后一个item，可能是独立的区间，也可能合并后进入维护区间，不论如何，在最后一次循环后总是会留下一个维护区间未加入答案中，这里加上
if(st!=-0x3f3f3f3f)ans.push_back({ st,ed });//if语句防止无输入的range
range = ans;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
ran.push_back({ l,r });
}
sort(ran.begin(), ran.end());
merge(ran);
cout << ran.size() << endl;
return 0;
}