LeetCode/56. 合并区间

56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例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] 可被视为重叠区间。

注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示：

• intervals[i][0] <= intervals[i][1]

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题在1288. 删除被覆盖区间的基础上更进一步，但是思路大同小异。首先对数组进行排序，按第一个元素升序，第二个元素降序排列。排列完成后需要考虑两种情况：1. 两个区间有交集，那么需要找出右边界最大的区间；2. 两个区间没有交集，直接将新区间添加进结果数组即可。

具体代码如下：

class Solution {
    public int[][] merge(int[][] intervals) {
        //判空操作
        if (intervals.length == 0)
            return new int[][]{};

        //对数组进行排序
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0])
                return b[1] - a[1];
            return a[0] - b[0];
        });

        //将排序后数组中的第一个元素加入结果链表中
        Deque<int[]> list = new LinkedList<>();
        int left = intervals[0][0];
        int right = intervals[0][1];
        list.add(new int[]{left, right});

        for (int i = 1; i < intervals.length; i++) {
            int[] temp = intervals[i];
            //如果两个区间不相交，直接添加新区间即可
            if (temp[0] > right) {
                left = temp[0];
                right = temp[1];
                list.add(new int[]{left, right});
            } else {
                //如果两个区间相交，找出最大的右边界
                int[] curr = list.removeLast();
                right = Math.max(curr[1], temp[1]);
                curr[1] = right;
                list.add(curr);
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}