区间的合并

给定 n个区间 [ $l_{i}$ , $r_{i}$ ]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3]和 [2,6]可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。

接下来 n行，每行包含两个整数 l和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤100000,
$-10^{9}$ ≤ $l_{i}$ ≤ $r_{i}$ ≤ $10^{9}$

输入样例：

输出样例：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;vector<PII> segs;void merge(vector<PII>& segs){//这里注意引用符号，关于引用的用法我前面有说过，这里就不说了。vector<PII> res;//定义装结果区间的vector数组res。sort(segs.begin(),segs.end());/*在操作之前，先将输入的一个个区间给排序，这里要注意，我们是用的vector<PII> segs;来存的，是pair<int,int>,相当于输入的{l,r}就是一个元素，数组里面有多少个元素，就说明有多少个区间，这一点我会在我写的博客里面细讲的。*/int st = -2e9,ed = -2e9;/*初始化定义开始值和结束值为-2e9，定义为-2e9是因为输入的是l,r两个，这里相当于定义的是无效值的感觉，说明此时还没有开始，区间里面还没有值。*/for(auto seg : segs){if(ed < seg.first){/*我的理解是：这个ed是当前操作区间的末尾点ed，而seg.first则是当前操作区间的下一个枚举区间，当当前操作区间的末尾点ed小于下一个枚举区间的开头seg.first的时候，就说明当前操作区间与下一个枚举区间之间没有交集，既然没有交集，那就将当前操作区间放入结果vector数组res里面。*/if(st != -2e9)  res.push_back({st,ed});//当前操作区间{st,ed}直接插入进去。/*刚开始我们初始化了st=-2e9，满足条件，要将当前操作区间放入结果数组里面的时候，要注意，不能让st等于初始值-2e9，不然会报错。*/st = seg.first,ed = seg.second;//将当前操作区间放入结果数组后，将st和ed两个更新为下一个枚举区间的st,ed的值，准备下一次操作}else ed = max(ed,seg.second);/*如果满足上面的条件，那就说明两个区间之间有交集，那么这个时候st是不动的，只需要将ed更新为两个区间中最大的那个ed值即可，就是求两个集合的并集。*/     }if(st != -2e9)   res.push_back({st,ed});/*注意，当遍历循环次数结束的时候，最后得到的那个区间是没办法加入到结果数组res里面的，所以这里判断，如果st不为初始值的化，那么就把此时的{st,ed}结果区间给插进去，就可以了。而且这个还有一个作用就是防止输入的区间是空的。*/segs = res;/*将得到的结果数组覆盖之前的segs数组，最后方便输出。所以这里可以看出来，res数组只是一个中间变量而已。*/
}int main(){int n;cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;segs.push_back({l,r});/*定义这个segs(vector)类型的是因为每一次输入的数都不一样，随着输入次数的变化。segs里面的内容也会随着变化，所以这种存变化的数据的就用可变数组vector来存。*/}merge(segs);/*输入之后就想着合并，注意，我们segs刚开始是存储的所有的输入的序列，为了输出和各方面的方便，我们也segs来作为结果输出，那么想做到这样就是在一个函数里面把结果给得到，然后把结果复制给segs，把segs原有的给覆盖，最后就可以输出了，就是下面的cout那句话了。*/cout<<segs.size()<<endl;/*res结果区间复制给segs区间，覆盖他，最后输出里面有几个区间元素就得到了结果了。*/return 0;
}

注意事项：

1、

这句代码 sort(segs.begin(), segs.end()); 是用来对容器 segs 中的元素进行排序的。具体来说：

segs 是一个存储区间的容器，比如一个 vector<pair<int, int>>。

sort(segs.begin(), segs.end()); 会对容器 segs 中的所有元素进行排序。