银川网站建设公司深圳网络推广系统
直接上题目,不废话!
题目
给定 n 个区间 [l,r]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。数据范围
1≤n≤100000,
−10e9≤l≤r≤10e9
输入样例：5 1 2 2 4 5 6 7 8 7 9
输出样例：3
思路
对于这n个区间,我们可以先用vector数组存放,然后再对左端点进行排序, 排完序后,后一个区间的左端点就一定大于等于前一个区间的左端点了,如图,蓝色是一个维护的区间,st和ed分别是维护区间的左右端点
相邻的两个区间只有这三种情况,绿色和红色可以归为一种,就是它的左端点小于等于蓝色的右端点,那我们的维护区间的右端点就要取(蓝色的右端点,对比区间的右端点)的最大值,当出现橙色这种情况就说明蓝色区间已经是一个答案区间了
代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;typedef pair <int,int> PII;
vector <PII> segs; //输入的初始区间数组int n;void merge(vector <PII> &segs)
{vector <PII> res; // 定义的答案区间数组sort(segs.begin(), segs.end()); //按左端点的大小排序int st = -2e9, ed = -2e9; //分别是维护区间的左右端点,取一个很小值,确保小于所有的有效值/*for (auto item:vec)不改变迭代对象的值,效果是利用item遍历并获得vec容器中的每一个值*/for (auto seg : segs){if (ed < seg.first) //维护区间的右端点和对比区间的左端点不相交就是已经是合并好了一个答案区间{if (ed != -2e9) //两个if(ed!=-2e9)是确保初始值不被加入到答案数组{res.push_back({ st,ed });}st = seg.first, ed = seg.second; //更新维护区间}else{ed = max(ed, seg.second);}}if(ed!=-2e9) //如果区间不为空,那么最后一个区间一定是一个独立的答案区间res.push_back({ st,ed });segs = res;
}
int main()
{cin >> n;while (n--){int l, r;cin >> l >> r;segs.push_back({ l,r });}merge(segs);cout << segs.size() << endl;return 0;
}