合并区间
题目描述：以数组 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)。
public class LeetCode_056 {
public static int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 1) {
return intervals;
}
int length = intervals.length, match = 0, matchFirst, matchSecond;
boolean[] flag = new boolean[length];
for (int i = 0; i < length; i++) {
if (!flag[i]) {
matchFirst = intervals[i][0];
matchSecond = intervals[i][1];
match++;
for (int j = i + 1; j < length && !flag[j]; j++) {
int curFirst = intervals[j][0], curSecond = intervals[j][1];
if (((matchFirst >= curFirst && matchFirst <= curSecond) || (matchSecond >= curFirst && matchSecond <= curSecond)) ||
((curFirst >= matchFirst && curFirst <= matchSecond) || (curSecond >= matchFirst && curSecond <= matchSecond))) {
// 有交集
matchFirst = Math.min(matchFirst, curFirst);
matchSecond = Math.max(matchSecond, curSecond);
intervals[i][0] = matchFirst;
intervals[i][1] = matchSecond;
flag[j] = true;
}
}
}
}
if (match == length) {
return intervals;
}
int[][] newIntervals = new int[match][2];
for (int i = 0, j = 0; i < length; i++) {
if (!flag[i]) {
newIntervals[j] = intervals[i];
j++;
}
}
return merge(newIntervals);
}
public static void main(String[] args) {
int[][] intervals = new int[][]{{1, 4}, {2, 3}};
for (int[] ints : merge(intervals)) {
for (int anInt : ints) {
System.out.print(anInt + " ");
}
System.out.println();
}
}
}
【每日寄语】 当你不开心的时候，你就可以吃一块糖果，然后告诉自己生活还是甜甜的，加油。
