刷刷刷 Day 36 | 56. 合并区间

56. 合并区间

LeetCode题目要求

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

示例

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

解题思路

1 3
2 6
8 10
15 18
以示例简单列出一个区间分布，有图可看出 [1,3] 和 [2,6] 存在重叠，那么需要合并
合并逻辑为，取区间左侧最小和右侧最大。
关键点在于找重叠区域，同时需要注意的是 [1,4] 和 [4,5] 也认为重叠
这题主要找到重叠，进行合并就好了

上代码

class Solution {
    public int[][] merge(int[][] intervals) {

        // 通过 LinkedList 来存储 区间
        LinkedList<int[]> res = new LinkedList<>();
        
        // 由于涉及到了重复区域判断，首先进行排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        // 第一区间入 list
        res.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间左边值 <= 前一个区间右边值，那么重叠
            if (intervals[i][0] <= res.getLast()[1]) {
                // 取前一区间的左边值 作为开始
                int start = res.getLast()[0];
                // 对比前后两个区间的右边，取大的，合并成一个新的区间
                int end = Math.max(intervals[i][1], res.getLast()[1]);
                // 移除那个将要被合并的区间
                res.removeLast();
                // 合并的新区间存储 结果
                res.add(new int[]{start, end});
            }
            else {
                // 如果不重叠，直接放入结果
                res.add(intervals[i]);
            }         
        }
        return res.toArray(new int[res.size()][]);
    }
}

附：学习资料链接