#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> pii;//定義 pair<int,int> 名字為PII
vector<pii> all,res;
int main(){int st=2e-9,ed=-2e9; //ed代表區(qū)間結(jié)尾，st代表區(qū)間開(kāi)頭.剛開(kāi)始兩個(gè)為最小值int n,l,r;cin >>n;for(int i=0;i<n;i++){//區(qū)間輸入cin >>l>>r;all.push_back({l,r});//將每個(gè)區(qū)間放入，方便之后遍歷}sort(all.begin(),all.end()); //區(qū)間左端點(diǎn)排序。優(yōu)先按左端點(diǎn)排序，再按右端點(diǎn)。//不可能有：區(qū)間2在區(qū)間1的左邊（因?yàn)槭桥胚^(guò)序的）for(auto num:all){if(ed<num.first){ //第一種情況：兩個(gè)區(qū)間無(wú)法合并。   區(qū)間1的末點(diǎn)<區(qū)間2的首點(diǎn)if(ed!=-2e9){res.push_back({st,ed});//將區(qū)間放入數(shù)組}st=num.first;//更新首尾,維護(hù)區(qū)間ed=num.second;}else if(ed<num.second){//第二種情況：兩個(gè)區(qū)間可以合并。 區(qū)間1的末點(diǎn)<區(qū)間2的末點(diǎn)ed=num.second;}}if(st!=2e-1&&ed!=2e-9){res.push_back({st,ed});//循環(huán)結(jié)束時(shí)的st,ed變量，此時(shí)的st,ed變量不需要繼續(xù)維護(hù)，只需要放進(jìn)res數(shù)組即可。因?yàn)檫@是最后的一個(gè)序列，所以不可能繼續(xù)進(jìn)行合并。}cout <<res.size();//求出區(qū)間數(shù)量return 0;
}

// 將所有存在交集的區(qū)間合并
void merge(vector<PII> &segs)
{vector<PII> res;sort(segs.begin(), segs.end());int st = -2e9, ed = -2e9;for (auto seg : segs)if (ed < seg.first){if (st != -2e9) res.push_back({st, ed});st = seg.first, ed = seg.second;}else ed = max(ed, seg.second);if (st != -2e9) res.push_back({st, ed});segs = res;
}

總結(jié)

以上是生活随笔為你收集整理的Awcing算法---区间合并的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。