给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
解题思路
将所有数组按首元素从小到大排序
遍历每个数组, 取出左右边界
如果当前结果集为空, 也就是刚遍历第一个数组
或者结果集中最后一个数组的右边界小于当前左边界, 意味着"断层", 所以无法合并
这两种情况都添加新元素
否则意味着可以合并, 调整结果集最后一个数组的右边界
代码
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> result = new ArrayList<>();
if (intervals == null || intervals.length == 0) {
return new int[0][];
}
// 根据首元素比较, 从小到大排序
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
for (int i = 0; i < intervals.length; i++) {
// 取出当前数组的左右边界
int left = intervals[i][0];
int right = intervals[i][1];
// 如果当前结果集为空, 或者结果集中最后一个数组的右边界小于当前左边界
// 意味着"断层", 所以无法合并, 添加新元素
if (result.size() == 0 || result.get(result.size() -1)[1] < left) {
result.add(new int[]{left, right});
} else { // 否则意味着可以合并, 调整结果集最后一个数组的右边界
result.get(result.size() - 1)[1] = Math.max(right, result.get(result.size() - 1)[1]);
}
}
return result.toArray(new int[0][]);
}
}
