題目描述

給定?n?個(gè)區(qū)間?[li,?ri]，要求合并所有有交集的區(qū)間。注意如果在端點(diǎn)處相交，也算有交集。
輸出合并完成后的區(qū)間個(gè)數(shù)。
例如：[1,?3]?和?[2,?6]?可以合并為一個(gè)區(qū)間?[1,?6]。

輸入格式

第一行包含整數(shù)?n?。
接下來(lái)?n?行，每行包含兩個(gè)整數(shù)?l?和?r。第?i?行的兩個(gè)數(shù)據(jù)表示?li,?ri。

輸出格式

共一行，包含一個(gè)整數(shù)，表示合并區(qū)間完成后的區(qū)間個(gè)數(shù)。

數(shù)據(jù)范圍

1≤n≤100,000

?10^9≤li≤ri≤10^9

輸入樣例

5
1 2
2 4
5 6
7 8
7 9

輸出樣例

3

注釋版代碼

//http://47.110.135.197/problem.php?id=5240
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
vector<PII> segs;
vector<PII> res;//res用于存放合并完的區(qū)間
void merge(vector<PII> &segs)
{sort(segs.begin(),segs.end());//先對(duì)區(qū)間進(jìn)行排序，pair排序是按照左斷點(diǎn)先排序，再按照右端點(diǎn)排序int st=-2e9,ed=-2e9;//將st和ed定義為極限小，因?yàn)轭}目的數(shù)據(jù)范圍是10^9，所以定義極限小可以定義2e9for(auto seg:segs){//對(duì)于兩區(qū)間之間的關(guān)系有兩種情況//①前面區(qū)間與后面區(qū)間沒有交集：那么沒有交集就說(shuō)明前面區(qū)間已經(jīng)不能與后面區(qū)間合并//那么前面的區(qū)間就已經(jīng)不能再合并了，可以放入結(jié)果集了if(ed<seg.first)//這樣定義ed=-2e9就可以保證第一個(gè)有效區(qū)間能進(jìn)行操作{if(st!=-2e9)//只要他不是我們?nèi)〉臒o(wú)限小，就可以放入結(jié)果集了{(lán)res.push_back({st,ed});}st=seg.first,ed=seg.second;//然后更新st為后面區(qū)間的l和r}//②前面區(qū)間與后面區(qū)間有交集：那么我們只需要把ed更新為前面區(qū)間和后面區(qū)間相比較大的右端點(diǎn)就可以了else ed=max(ed,seg.second);}if(st!=-2e9) res.push_back({st,ed});//如果只有一個(gè)區(qū)間，我們就需要用到這個(gè)步驟
}
int main()
{int n,l,r;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d %d",&l,&r);segs.push_back({l,r});//將每一個(gè)lr代表的區(qū)間存入segs里面}merge(segs);//對(duì)segs區(qū)間進(jìn)行合并操作printf("%d",res.size());//輸出合并完的區(qū)間個(gè)數(shù)return 0;
}