56. 合并区间 - 力扣（LeetCode）

一、题目

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

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

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

二、代码

class Solution {
    public int[][] merge(int[][] intervals) {
        // 如果为空，直接返回（0，0）区间
        if (intervals == null || intervals.length == 0) {
            return new int[][] {{0, 0}};
        }

        // 按照区间的开始位置从小到大排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        // 记录当前正在统计合并区间的开始位置
        int s = intervals[0][0];
        // 记录当前正在统计合并区间的结束位置
        int e = intervals[0][1];
        // 当前要返回的答案已经填到什么位置了
        int size = 0;

        // 遍历所有区间，将答案复用填到intervals中
        for (int i = 1; i < intervals.length; i++) {
            // 如果当前遍历到的区间的开始位置大于当前正在统计合并区间的结束位置，说明我们遍历的区间出现了断档，无法和前面的区间连在一起
            // 所以记录一个独立区间的答案，然后重新开始统计一段新的区间
            if (intervals[i][0] > e) {
                // 将当前已经合并的区间记录在要返回的答案中
                intervals[size][0] = s;
                intervals[size++][1] = e;
                // 以当前新遍历到的区间来继续合并统计
                s = intervals[i][0];
                e = intervals[i][1];
            // 如果当前遍历到的区间的开始位置小于等于当前正在统计合并区间的结束位置，说明这两个区间还是能合并成一个的，他们是连在一起的
            } else {
                // 去看哪一个区间的结束位置能推高e，就将哪个赋值给e，完成两段区间的合并
                e = Math.max(e, intervals[i][1]);
            }
        }

        // 将最后一个还没来得及加入到结果中的区间加入进去
        intervals[size][0] = s;
        intervals[size++][1] = e;
        // 将要返回的答案进行数组创建，并返回，只需要返回intervals数组中长度为size的部分即可
        return Arrays.copyOf(intervals, size);
    }
}

三、解题思路 

开始位置从小到大排序，根据第一维数据排序，开始位置谁靠前谁排在前面。

遍历所有的区间范围，看后面区间的开始位置能不能包含在前面区间的结束位置内，如果不能就要新开一个区间；如果能就合并成一个区间。本质就是排序后看两个相邻的区间是不是连在一起的，连在一起的区间就合并成一个区间即可。