LeetCode 56. 合并区间---代码逐行剖析

题目简述：二维数组?intervals?为若干个区间的集合，其中单个区间为?intervals[i] = [starti, endi]?。合并所有重叠的区间，并返回一个不重叠的区间数组。

例如：

将 [[1,3],[2,6],[8,10],[15,18]] 合并为 [[1,6],[8,10],[15,18]]

代码如下：

public static int[][] merge(int[][] intervals) {
	// 根据子数组的区间左边界进行排序
	Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
	// ans：用于暂时存放结果的数组
	int[][] ans = new int[intervals.length][2];
	//idx：偏移量，也用作计数
	int idx = -1;
	//遍历二维数组，interval为单个数组区间
	for (int[] interval : intervals) {
		if (idx == -1 || ans[idx][1] < interval[0]) { //解读一
			//把区间加入结果中
			ans[++idx] = interval;
		} else {
			//取右边界的最大值
			ans[idx][1] = Math.max(ans[idx][1], interval[1]);
		}
	}

	return Arrays.copyOf(ans, idx + 1);//解读二
}

有关 Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]); 的解释，请参考我的另一篇文章：Java重写Arrays.sort(intervals, (v1, v2) -＞ v1[0] - v2[0])详解---Lambda重写简化版

---

解读一

区间的左边界为interval[0]，右边界为interval[1]

当结果数组ans没有加过区间时（idx == 1），或者此时ans中，idx对应的区间右边界ans[idx][1]（也是ans中最大的右边界）比遍历到的区间左边界interval[0]小，即区间不重叠，就把区间放入ans中

否则取右边界的最大值。前面是根据左边界进行排序的，所以右边界的大小有如下两种情况

---

解读二

返回结果为什么用到了Arrays.copyOf()？

为什么没有直接返回ans呢，注意到我们在创建ans的时候，一维的长度是intervals.length。新建的ans数组打印如下（参考文章开头的例子），因为我们要合并重叠的区间，所以最终的长度肯定会小于等于原数组interval的长度

[[0, 0],[0, 0],[0, 0],[0, 0]]

?当区间合并完之后，打印如下：

[[1, 6],[8, 10],[15, 18],[0, 0]]

?可以看到有一个多余的区间[0, 0]，而目标区间数应该是idx + 1，所以要返回ans的前idx + 1个区间

[[1, 6],[8, 10],[15, 18]]

---

本文参考了LeetCode相关题解，并根据自己的理解做了进一步解读，希望对你有帮助。