合并区间

题目描述：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）   

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：递归

递归的过程如下：

• 如果intervals为空或者intervals只有一个元素即只有1个区间，不需要合并处理，直接返回intervals；

• 如果intervals不止有1个元素，声明一个变量length记录intervals一维的长度（即有多少个区间），变量match记录不需要合并的区间的数量，matchFirst和matchSecond记录当前需要匹配的区间的2个数，然后再声明一个boolean数组flag记录区间是否已经被合并，然后用双重循环来判断那些区间是可以合并的，处理过程如下：

• 外层循环i是第一个区间开始，matchFirst和matchSecond记录i对应区间的2个值并且match加1；

• 内层循环j从第i+1个区间开始，curFirst和curSecond记录j对应区间的2个值，然后用matchFirst、matchSecond、curFirst、curSecond来判断i和j这2个区间是否有交集，如果有交集，则更新i区间的2个数，并更新matchFirst和matchSecond，并且将j的区间标记为true即已被合并；如果没有交集，则处理下一个；

• 双重循环处理完后，判断match和length是否相等，如果相等，说明没有可合并的区间，返回intervals；如果不相等，则初始化一个新的二维数组newIntervals，将intervals中没有被合并的区间（根据flag数组判断是否已被合并）拷贝到newIntervals，然后递归调用merge(newIntervals)。

【每日寄语】 当你不开心的时候，你就可以吃一块糖果，然后告诉自己生活还是甜甜的，加油。