區(qū)間合并是什么？
我們要了解區(qū)間合并是什么，首先來看這樣的一個例子。
區(qū)間2是區(qū)間1的一個子區(qū)間
區(qū)間3和區(qū)間1有交集
區(qū)間4和區(qū)間1端點在同一個點上
區(qū)間5和區(qū)間1沒有交集
所以區(qū)間2,3，4都可以和區(qū)間1合并形成一個新的區(qū)間，區(qū)間5則不行。
總結(jié)：區(qū)間合并就是把多個區(qū)間有交集的部分，快速進行合并。
接下來我們通過一個例子來快速體驗一下區(qū)間合并
例1
問題描述
給定2個閉區(qū)間 [a1,b1],[a2,b2]，判斷這兩個區(qū)間能否合并成為一個新的區(qū)間。
任意兩個相鄰或相交的閉區(qū)間可以合并為一個閉區(qū)間。例如，[1,2] 和 [2,3] 可以合并為[1,3] ；[1,3] 和 [2,4] 可以合并為 [1,4]，但是 [1,2] 和 [3,4] 不可以合并。
我們的任務是判斷這兩個區(qū)間是否可以最終合并為一個閉區(qū)間，如果可以，輸出 Yes，否則輸出 No。
輸入
一共兩行。
第一行兩個整數(shù)a1,b1 ，表示第一個區(qū)間。
第二行兩個整數(shù) a2,b2，表示第二個區(qū)間。
輸出
兩個區(qū)間是否可以最終合并為一個閉區(qū)間，如果可以，輸出 Yes，否則輸出 No。
數(shù)據(jù)規(guī)模
-1018 <=a1,b1,a2,b2<=1018
輸入輸出
樣例1
輸入：
1 2
2 3
輸出：
Yes
樣例2
輸入：
3 5
8 9
輸出：
No
樣例3
輸入：
3 8
1 3
輸出：
Yes
思路分析
對于這題因為只有兩個區(qū)間，我們只需要將區(qū)間進行排序確保第一個區(qū)間的左端點是最小的，然后判斷第一個區(qū)間的右端點是否小于第二個區(qū)間的左端點就好了。
代碼
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main(void)
{
vector<pair<long long, long long>> segs;//用一個二元組來存放輸入，因為數(shù)據(jù)量比較大所以用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());//對區(qū)間進行排序，確保第一個區(qū)間的左端點是最小的
if (segs[0].second < segs[1].first) cout << "No" << endl;//只要大于或者等于都是可以合并的
else cout << "Yes" << endl;
return 0;
}
在了解了一個例子之后，大家對區(qū)間合并一定都有了一定的認識，接下來我們通過另一個例子來加深對區(qū)間合并的了解。
例2
問題描述
給定2個閉區(qū)間 [a1,b1],[a2,b2]，判斷這兩個區(qū)間能否合并成為一個新的區(qū)間。
任意兩個相鄰或相交的閉區(qū)間可以合并為一個閉區(qū)間。例如，[1,2] 和 [2,3] 可以合并為[1,3] ；[1,3] 和 [2,4] 可以合并為 [1,4]，但是 [1,2] 和 [3,4] 不可以合并。
我們的任務是判斷這兩個區(qū)間是否可以最終合并為一個閉區(qū)間，如果可以，輸出合并的新區(qū)間，否則輸出-1 。
輸入
一共兩行。
第一行兩個整數(shù)a1,b1 ，表示第一個區(qū)間。
第二行兩個整數(shù) a2,b2，表示第二個區(qū)間。
輸出
如果可以合并，輸出合并后的新區(qū)間坐標。如果不可以，輸出 -1。
數(shù)據(jù)規(guī)模
-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
思路分析
這題和上題的區(qū)別就是這題如果可以合并，那我們就需要輸出新區(qū)間的左右端點了，所以我們只需要把最小的左端點和最大的右端點給記錄下來就好了，對于最小的左端點就是第一個區(qū)間的左端點，因為我們在判斷之前就已經(jīng)對數(shù)據(jù)進行了排序，確保了第一個區(qū)間的左端點是最小區(qū)間。
代碼
#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;
}
通過這一個例子之后，大家對區(qū)間合并一定有了更深的認識，接下來我們通過一個例子來學會如何處理2個以上的區(qū)間
例3
問題描述
給定n個閉區(qū)間 [ai,bi]，其中i = 1,2,…,n。
任意兩個相鄰或相交的閉區(qū)間可以合并為一個閉區(qū)間。例如，[1,2] 和 [2,3] 可以合并為[1,3] ；[1,3] 和 [2,4] 可以合并為 [1,4]，但是 [1,2] 和 [3,4] 不可以合并。
我們的任務是判斷這些區(qū)間是否可以最終合并為一個閉區(qū)間，如果可以，將這個閉區(qū)間輸出，否則輸出 no。
輸入
第一行為一個整數(shù)n(3<= n <=50,000) 。表示輸入?yún)^(qū)間的數(shù)量。
之后 n 行，在第 i(1<=i<=n) 行上，為兩個整數(shù) ai,bi，整數(shù)之間用一個空格分隔，表示區(qū)間 [ai,bi]（其中 1 <= ai <= bi <= 10,000）。
輸出
輸出一行，如果這些區(qū)間最終可以合并為一個閉區(qū)間，輸出這個閉區(qū)間的左右邊界，用單個空格隔開；否則輸出 no。
輸入輸出
樣例1
輸入：
5
5 6
1 5
10 10
6 9
8 10
輸出：
1 10
思路分析
對于這題，我們只需要遍歷一下所有的區(qū)間，當其中有一個區(qū)間的右端點小于它下一個區(qū)間的左端點說明就不能合并成一個區(qū)間，每次迭代之后更新一下右端點的值為最大的那個就好了。
代碼
#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;//確保第一個區(qū)間一定小于初始值
sort(segs.begin(), segs.end());
st = segs[0].first;//因為已經(jīng)排過序了，所以第一個區(qū)間的左端點是最小的
bool sign = true;//標記一下是否可以合并
for (auto seg : segs)
{
if (st > seg.first) st = seg.first;
if (ed < seg.first && ed != -1e8) {//如果有某個區(qū)間的右端點小于它的下一個區(qū)間的左端點那就表示不能合并
cout << "no" << endl;
sign = false;//標記一下然后退出循環(huán)
break;
}
else {
ed = seg.second;
}
}
if (sign) cout << st << ' ' << ed << endl;
return 0;
}
相信大家都已經(jīng)掌握了區(qū)間合并，接下來我們來通過一個例子檢驗一下~
例4
問題描述
給定 n 個區(qū)間 [li,ri]，要求合并所有有交集的區(qū)間。注意如果在端點處相交，也算有交集。
輸出合并完成后的區(qū)間個數(shù)。
例如：[1,3] 和 [2,6] 可以合并為一個區(qū)間 [1,6]。
輸入
第一行包含整數(shù) n(1<=n<=100,000)。
接下來 n 行，每行包含兩個整數(shù) l 和 r。第 i 行的兩個數(shù)據(jù)表示 li，ri,(-109<=li<=ri<=109)。
輸出
共一行，包含一個整數(shù)，表示合并區(qū)間完成后的區(qū)間個數(shù)。
輸入輸出
樣例1
輸入：
5
1 2
2 4
5 6
7 8
7 9
輸出：
3文章來源：http://www.zghlxwxcb.cn/news/detail-624209.html
參考代碼
#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;
}
歡迎大家評論區(qū)討論和交流哦~ 有我沒說清楚的地方可以私信問我。文章來源地址http://www.zghlxwxcb.cn/news/detail-624209.html
到了這里，關于區(qū)間合并（超詳細逐步講解/例題/思路分析/參考代碼）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
