区间合并超详解
- 区间合并是什么？
- 例1
- 问题描述
- 输入
- 输出
- 数据规模
- 输入输出
- 思路分析
- 代码
- 例2
- 问题描述
- 输入
- 输出
- 数据规模
- 输入输出
- 思路分析
- 代码
- 例3
- 问题描述
- 输入
- 输出
- 输入输出
- 思路分析
- 代码
- 例4
- 问题描述
- 输入
- 输出
- 输入输出
- 参考代码
区间合并是什么？
我们要了解区间合并是什么，首先来看这样的一个例子。
区间2是区间1的一个子区间
区间3和区间1有交集
区间4和区间1端点在同一个点上
区间5和区间1没有交集
所以区间2,3，4都可以和区间1合并形成一个新的区间，区间5则不行。
总结：区间合并就是把多个区间有交集的部分，快速进行合并。
接下来我们通过一个例子来快速体验一下区间合并
例1
问题描述
给定2个闭区间 [a1,b1],[a2,b2]，判断这两个区间能否合并成为一个新的区间。
任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1,2] 和 [2,3] 可以合并为[1,3] ；[1,3] 和 [2,4] 可以合并为 [1,4]，但是 [1,2] 和 [3,4] 不可以合并。
我们的任务是判断这两个区间是否可以最终合并为一个闭区间，如果可以，输出 Yes，否则输出 No。
输入
一共两行。
第一行两个整数a1,b1 ，表示第一个区间。
第二行两个整数 a2,b2，表示第二个区间。
输出
两个区间是否可以最终合并为一个闭区间，如果可以，输出 Yes，否则输出 No。
数据规模
-1018 <=a1,b1,a2,b2<=1018
输入输出
样例1
输入：
1 2
2 3
输出：
Yes
样例2
输入：
3 5
8 9
输出：
No
样例3
输入：
3 8
1 3
输出：
Yes
思路分析
对于这题因为只有两个区间，我们只需要将区间进行排序确保第一个区间的左端点是最小的，然后判断第一个区间的右端点是否小于第二个区间的左端点就好了。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main(void)
{
vector<pair<long long, long long>> segs;//用一个二元组来存放输入，因为数据量比较大所以用long long 类型。
for (int i = 0; i < 2; i++)
{
long long st, ed;
scanf("%lld%lld", &st, &ed);
segs.push_back({ st,ed });
}
sort(segs.begin(), segs.end());//对区间进行排序，确保第一个区间的左端点是最小的
if (segs[0].second < segs[1].first) cout << "No" << endl;//只要大于或者等于都是可以合并的
else cout << "Yes" << endl;
return 0;
}
在了解了一个例子之后，大家对区间合并一定都有了一定的认识，接下来我们通过另一个例子来加深对区间合并的了解。
例2
问题描述
给定2个闭区间 [a1,b1],[a2,b2]，判断这两个区间能否合并成为一个新的区间。
任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1,2] 和 [2,3] 可以合并为[1,3] ；[1,3] 和 [2,4] 可以合并为 [1,4]，但是 [1,2] 和 [3,4] 不可以合并。
我们的任务是判断这两个区间是否可以最终合并为一个闭区间，如果可以，输出合并的新区间，否则输出-1 。
输入
一共两行。
第一行两个整数a1,b1 ，表示第一个区间。
第二行两个整数 a2,b2，表示第二个区间。
输出
如果可以合并，输出合并后的新区间坐标。如果不可以，输出 -1。
数据规模
-1018 <=a1,b1,a2,b2<=1018
输入输出
样例1
输入：
1 2
2 3
输出：
1 3
样例2
输入：
3 8
1 3
输出：
1 8
样例3
输入：
3 5
8 9
输出：
-1
思路分析
这题和上题的区别就是这题如果可以合并，那我们就需要输出新区间的左右端点了，所以我们只需要把最小的左端点和最大的右端点给记录下来就好了，对于最小的左端点就是第一个区间的左端点，因为我们在判断之前就已经对数据进行了排序，确保了第一个区间的左端点是最小区间。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main(void)
{
vector<pair<long long, long long>> segs;
for (int i = 0; i < 2; i++)
{
long long st, ed;
scanf("%lld%lld", &st, &ed);
segs.push_back({ st,ed });
}
sort(segs.begin(), segs.end());
if (segs[0].second < segs[1].first) cout << -1 << endl;
else
{
long long x = segs[1].second > segs[0].second ? segs[1].second : segs[0].second;//把最大的右端点更新一下
cout << segs[0].first << ' ' << x << endl;
}
return 0;
}
通过这一个例子之后，大家对区间合并一定有了更深的认识，接下来我们通过一个例子来学会如何处理2个以上的区间
例3
问题描述
给定n个闭区间 [ai,bi]，其中i = 1,2,…,n。
任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1,2] 和 [2,3] 可以合并为[1,3] ；[1,3] 和 [2,4] 可以合并为 [1,4]，但是 [1,2] 和 [3,4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出 no。
输入
第一行为一个整数n(3<= n <=50,000) 。表示输入区间的数量。
之后 n 行，在第 i(1<=i<=n) 行上，为两个整数 ai,bi，整数之间用一个空格分隔，表示区间 [ai,bi]（其中 1 <= ai <= bi <= 10,000）。
输出
输出一行，如果这些区间最终可以合并为一个闭区间，输出这个闭区间的左右边界，用单个空格隔开；否则输出 no。
输入输出
样例1
输入：
5
5 6
1 5
10 10
6 9
8 10
输出：
1 10
思路分析
对于这题，我们只需要遍历一下所有的区间，当其中有一个区间的右端点小于它下一个区间的左端点说明就不能合并成一个区间，每次迭代之后更新一下右端点的值为最大的那个就好了。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main(void)
{
int n;
cin >> n;
vector<pair<int, int>>segs;//用一个二元组来存储输入
for (int i = 0; i < n; i++)
{
int st, ed;
scanf("%d%d", &st, &ed);
segs.push_back({ st,ed });
}
int st = 1e8, ed = -1e8;//确保第一个区间一定小于初始值
sort(segs.begin(), segs.end());
st = segs[0].first;//因为已经排过序了，所以第一个区间的左端点是最小的
bool sign = true;//标记一下是否可以合并
for (auto seg : segs)
{
if (st > seg.first) st = seg.first;
if (ed < seg.first && ed != -1e8) {//如果有某个区间的右端点小于它的下一个区间的左端点那就表示不能合并
cout << "no" << endl;
sign = false;//标记一下然后退出循环
break;
}
else {
ed = seg.second;
}
}
if (sign) cout << st << ' ' << ed << endl;
return 0;
}
相信大家都已经掌握了区间合并，接下来我们来通过一个例子检验一下~
例4
问题描述
给定 n 个区间 [li,ri]，要求合并所有有交集的区间。注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入
第一行包含整数 n(1<=n<=100,000)。
接下来 n 行，每行包含两个整数 l 和 r。第 i 行的两个数据表示 li，ri,(-109<=li<=ri<=109)。
输出
共一行，包含一个整数，表示合并区间完成后的区间个数。
输入输出
样例1
输入：
5
1 2
2 4
5 6
7 8
7 9
输出：
3
参考代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int,int>> merges(vector<pair<int, int>> segs)
{
vector<pair<int, int>> temp;
int st = -1e9, ed = -1e9;
sort(segs.begin(), segs.end());
for (auto seg : segs)
{
if (ed < seg.first)
{
if (ed != -1e9) temp.push_back({ st,ed });
st = seg.first; ed = seg.second;
}
else ed = max(ed, seg.second);
}
if (st != -1e9) temp.push_back({ st,ed });
return temp;
}
int main(void)
{
int n;
cin >> n;
vector<pair<int, int>>segs;
for (int i = 0; i < n; i++)
{
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({ l,r });
}
auto t = merges(segs);
cout << t.size() << endl;
return 0;
}
欢迎大家评论区讨论和交流哦~ 有我没说清楚的地方可以私信问我。
