主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)二維整數(shù)陣列 ranges，其中 ranges[i] = [starti, endi] 代表著第 i 個(gè)區(qū)段包含著所有介於 starti（含）到 endi（含）之間整數(shù)。
你需要將這些區(qū)段分成兩組群組（可能為空）使得：
每一個(gè)區(qū)段屬於恰好一個(gè)群組、
任兩個(gè)彼此重疊的區(qū)段屬於同一個(gè)群組。
兩個(gè)區(qū)段如果存在著至少一個(gè)整數(shù)同時(shí)出現(xiàn)於兩者之中，則這兩個(gè)區(qū)段「彼此重疊」。
例如，[1, 3] 和 [2, 5] 是彼此重疊的，因?yàn)?2 和 3 同時(shí)出現(xiàn)在兩個(gè)區(qū)段之中。
回傳將所有區(qū)段切成兩個(gè)群組的所有可行方法數(shù)。由於答案可能會(huì)很大，將其模 10 ^ 9 + 7 後再回傳。
（譯者注：這邊沒有寫明，但是兩個(gè)群組是「相異」個(gè)體。意即你把所有區(qū)段丟在「某個(gè)」群組和把所有區(qū)段丟到「另一個(gè)」群組是「不一樣」的方法。參見範(fàn)例測(cè)資。）
限制：
1 ≦ ranges.length ≦ 10 ^ 5
ranges[i].length == 2
0 ≦ starti ≦ endi ≦ 10 ^ 9
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： ranges = [[6,10],[5,15]]
輸出： 2
解釋：
兩個(gè)區(qū)段彼此重疊，所以它們必須是在同一個(gè)群組中。
因此，有兩種可能的方式：
- 將兩個(gè)區(qū)段一起放到 1 號(hào)群組。
- 將兩個(gè)區(qū)段一起放到 2 號(hào)群組。
範(fàn)例 2：
輸入： ranges = [[1,3],[10,20],[2,5],[4,8]]
輸出： 4
解釋：
區(qū)段 [1,3] 和 [2,5] 彼此重疊，所以它們必須是在同一個(gè)群組中。
而區(qū)段 [2,5] 和 [4,8] 彼此重疊，所以它們必須也是在同一個(gè)群組中。
因此，有四種可能的方式分組：
- 所有區(qū)段在 1 號(hào)群組。
- 所有區(qū)段在 2 號(hào)群組。
- 區(qū)段 [1,3] 、 [2,5] 和 [4,8] 在 1 號(hào)群組，而 [10,20] 在 2 號(hào)群組。
- 區(qū)段 [1,3] 、 [2,5] 和 [4,8] 在 2 號(hào)群組，而 [10,20] 在 1 號(hào)群組。
解題思維：
用這題的想法加上併查集（Union-Find Set，參見這題的介紹）來將所有應(yīng)在一起的區(qū)段先分出一些團(tuán)體。這些團(tuán)體內(nèi)部的元素存在著另一個(gè)與其彼此重疊的元素，而對(duì)於團(tuán)體外的元素則沒有。
假設(shè)有 c 個(gè)這樣子的團(tuán)體，則答案即為 2 ^ c。記得用快速冪（參見這題古老心得文）來求此值並在過程中求模數(shù)。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
