题目描述
给定 n个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−10^9≤li≤ri≤10^9,
大体思路
从题目上看，会给我们几个区间，要我们求合并之后，有多少个交集，端点处相交也算交集，那想一下，会出现几种情况？可能有部分相交（包括端点相交），一种是一个在另一个里面，最后一种是两个毫无交点：
那这就是合并区间能遇到的所有情况，废话不多说，奉上代码：
usingnamespacestd; intn; vector<pair<int, int>>sec;//用于存放区间的两个端点voidmerge(vector<pair<int, int>>&sec) { vector<pair<int, int>>res;//用于存放合并好的区间sort(sec.begin(), sec.end());//将区间内部进行排序，pair类型排序默认先先用第一个排序，当第一个数字相同时候在比较第二个intl=-2e9, r=-2e9; //遍历一下数组，合并区间for (autoitme : sec) { if (r<itme.first)//如果现在维护的区间的右端点是小于遍历到的左端点的时候，说明维护的区间和所有区间没有交集，进入进行下一步操作 { if (l!=-2e9)res.push_back({ l,r });//当维护区间的左端点不是边界的时候，就将这个区间放入到合并区间的容器当中l=itme.first, r=itme.second;//更新维护区间 } //如果不是小于，则说明区间有交集，合并区间，将维护区间的右端点进行更新elser=max(r, itme.second);//对比哪个大，然后进行更新区间 } if (l!=-2e9)res.push_back({ l,r });//检查一下是否还有数组没有放进来，如果有就放进来sec=res;//将sec的内容更新成res的} intmain() { cin>>n; for (inti=0; i<n; i++) { intl, r; cin>>l>>r; sec.push_back({ l,r });//将区间两个端点放入到容器当中 } merge(sec);//合并区间cout<<sec.size() <<endl; return0; }
