合并区间 | LeetCode-56

分类不好，这道题就做不出来！

---

LeetCode链接：56. 合并区间

---

1.题目描述

以数组 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 <= 10^4$
• intervals[i].length == 2
• $0 <= start_i <= end_i <= 10^4$

2.题解

class Solution {
    public int[][] merge(int[][] intervals) {
        // 如果区间数组为空，直接返回空数组
        if(intervals.length == 0) return new int[0][2];

        // 将区间数组按每个区间的起始位置进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] intervals1, int[] intervals2) {
                // 按照区间的起始值升序排列
                return intervals1[0] - intervals2[0];
            }
        });

        // 用来保存合并后的区间
        List<int[]> result = new ArrayList<>();

        // 遍历所有区间
        for(int i = 0; i < intervals.length; i++) {
            // 当前区间的左边界 L 和右边界 R
            int L = intervals[i][0], R = intervals[i][1];

            // 如果 result 为空，或者 result 中最后一个区间的右边界小于当前区间的左边界
            // 说明当前区间与前一个区间没有重叠，直接添加当前区间
            if(result.size() == 0 || result.get(result.size() - 1)[1] < L) {
                result.add(new int[]{L, R});
            } else {
                // 否则，说明当前区间和前一个区间有重叠
                // 将最后一个区间的右边界更新为两个区间中较大的右边界，合并区间
                resultList.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], R);
            }
        }

        // 将结果列表转换为二维数组形式并返回
        return result.toArray(new int[result.size()][]);
    }
}