給定?n?個(gè)區(qū)間?[l,r]，要求合并所有有交集的區(qū)間。

注意如果在端點(diǎn)處相交，也算有交集。

輸出合并完成后的區(qū)間個(gè)數(shù)。

例如：[1,3]?和?[2,6]?可以合并為一個(gè)區(qū)間?[1,6]。

輸入格式

第一行包含整數(shù)?n。

接下來?n?行，每行包含兩個(gè)整數(shù)?l?和?r。

輸出格式

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

區(qū)間合并思路

首先，按區(qū)間左端點(diǎn)進(jìn)行排序。

其次，依次判斷是否存在交集。

對(duì)于判斷交集而言，在排序之后，區(qū)間的關(guān)系有三種可能。

1.區(qū)間A包含了區(qū)間B。

2.區(qū)間A與區(qū)間B有交集。

3.區(qū)間A與區(qū)間B沒有關(guān)系。

1.2.條件符合區(qū)間合并的要求，從中也可以得出比較的條件，即出區(qū)間A的右端點(diǎn)>=區(qū)間A的左端點(diǎn)（=是因?yàn)槎它c(diǎn)處相交，也算有交集）。

由于只需統(tǒng)計(jì)合并完成后的區(qū)間數(shù)量，因此需要先記錄區(qū)間總數(shù)，每當(dāng)合并的時(shí)候減一。

而為了提高效率，在判斷完需要合并區(qū)間之后，直接更新接下要比較的區(qū)間，使之成為之前需要合并的區(qū)間。

比如，有區(qū)間A,B,C（左端點(diǎn)有序）。區(qū)間A和B判斷完需要合并后，直接更新B，使B區(qū)間為原來A和B的合并區(qū)間，再將新的B區(qū)間和C比較。

這樣一來，就可以快速統(tǒng)計(jì)需要合并區(qū)間的數(shù)量了。

sort 排序的是一給左閉右開的區(qū)間。 （即取得到最左邊元素，但取不到最右邊元素）

而對(duì)于sort(a+1, a+1+n)而言，覆蓋的范圍是a[1] - a[n]。

此外，a的效果等同于a[0]，所以a + 1就是a[1]，a + 1 + n就是a[n + 1]，因?yàn)閟ort左閉右開的特性，所以不取a[n + 1]，只取到a[n]。

至于這里的pair就是將兩個(gè)變量關(guān)聯(lián)在一起,可以認(rèn)為是結(jié)構(gòu)體,不過只有兩個(gè)變量,而且pair排序的時(shí)候,優(yōu)先第一位,這樣可以快速實(shí)現(xiàn)區(qū)間左端點(diǎn)進(jìn)行排序。

開心，這比離散化簡單多了。