014.合并区间

56. 合并区间

以数组 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

题目思路

本题的本质是判断重叠区间问题。

对于这类问题，我们需要先对区间进行排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。

按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即 intervals[i] 的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重叠，所以是<=）

这么说有点抽象，看图：（注意图中区间都是按照左边界排序之后了）

知道如何判断重复之后，剩下的就是合并了，如何去模拟合并区间呢？

其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到 result 数组里就可以了。如果没有合并就把原区间加入到 result 数组。

在代码实现层面，我们需要一个LinkedList类型的变量模拟栈的操作，存储合并后的区间，默认先将排序后的第一个区间加入该变量中，然后依次遍历区间，判断是否重复**「如果后面的区间的左边界 小于等于 前面的区间的右边界，说明有区间重叠」**，如果重复，则将重复的区间弹出，计算合并后的区间左右边界后，加入合并后的区间，如果没有重复，则直接加入到该变量中即可

题解代码

public int[][] merge(int[][] intervals) {
    LinkedList<int[]> res = new LinkedList<>();
    // 按照区间的左边界将区间排序
    Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
    // 默认加入第一个区间
    res.add(intervals[0]);
    for (int i = 1; i < intervals.length; i++) {
        // 如果后面的区间的左边界 小于等于 前面的区间的右边界，说明有区间重叠
        if (intervals[i][0] <= res.getLast()[1]) {
            // 合并后的区间左边界为前面区间的左边界（因为是排好序的）
            int left = res.getLast()[0];
            // 合并后的区间右边界为两个重叠区间的更大的右边界；
            int right = Math.max(res.getLast()[1], intervals[i][1]);
            // 删除最后一个区间
            res.removeLast();
            // 加入合并后的区间
            res.addLast(new int[]{left, right});
        } else {
            // 没有区间重叠，直接添加
            res.addLast(intervals[i]);
        }
    }
    return res.toArray(new int[res.size()][]);
}