合并區(qū)間

題目描述：以數(shù)組 intervals 表示若干個區(qū)間的集合，其中單個區(qū)間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區(qū)間，并返回一個不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間。

示例說明請見LeetCode官網。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/merge-intervals/ ??

著作權歸領扣網絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

解法一：遞歸

遞歸的過程如下：

• 如果intervals為空或者intervals只有一個元素即只有1個區(qū)間，不需要合并處理，直接返回intervals；

• 如果intervals不止有1個元素，聲明一個變量length記錄intervals一維的長度（即有多少個區(qū)間），變量match記錄不需要合并的區(qū)間的數(shù)量，matchFirst和matchSecond記錄當前需要匹配的區(qū)間的2個數(shù)，然后再聲明一個boolean數(shù)組flag記錄區(qū)間是否已經被合并，然后用雙重循環(huán)來判斷那些區(qū)間是可以合并的，處理過程如下：

• 外層循環(huán)i是第一個區(qū)間開始，matchFirst和matchSecond記錄i對應區(qū)間的2個值并且match加1；

• 內層循環(huán)j從第i+1個區(qū)間開始，curFirst和curSecond記錄j對應區(qū)間的2個值，然后用matchFirst、matchSecond、curFirst、curSecond來判斷i和j這2個區(qū)間是否有交集，如果有交集，則更新i區(qū)間的2個數(shù)，并更新matchFirst和matchSecond，并且將j的區(qū)間標記為true即已被合并；如果沒有交集，則處理下一個；

• 雙重循環(huán)處理完后，判斷match和length是否相等，如果相等，說明沒有可合并的區(qū)間，返回intervals；如果不相等，則初始化一個新的二維數(shù)組newIntervals，將intervals中沒有被合并的區(qū)間（根據(jù)flag數(shù)組判斷是否已被合并）拷貝到newIntervals，然后遞歸調用merge(newIntervals)。

【每日寄語】 當你不開心的時候，你就可以吃一塊糖果，然后告訴自己生活還是甜甜的，加油。