14.合并区间

raylan.chen大约 3 分钟

以下代码思路，当遇到：

intervals = [[1,3],[2,6],[8,10],[15,18]]

输出：

[[1,6],[8,10],[15,18],[15,18]]

预期结果：

[[1,6],[8,10],[15,18]]

代码存在较多问题：

首先，第二层 for 循环中的截止条件 j < list.size() 中的list.size() 在循环过程中会变化，从而导致一些无意义的遍历；

其次，第二层for循环的判断else if (intervals[i][0] > tmp[1] || intervals[i][1] < tmp[0])会出现list 中[1, 6], [8, 10]都满足情况，从而导致出现两个[15, 18]。

class Solution {
    public int[][] merge(int[][] intervals) {
        // 遍历 intervals，list 存储结果
        List<int[]> list = new ArrayList<>();
        // [[1,3],[2,6],[8,10],[15,18]]
        for (int i = 0; i < intervals.length; i++) {
            if (list.size() == 0) {
                list.add(intervals[0]);
                continue;
            }
            for (int j = 0; j < list.size(); j++) {
                int[] tmp = list.get(j);
                // 需要合并情况：
                // res-start <= inter-start <= res-end && inter-end < res-end
                // inter-start < res-start && res-start <= inter-end <= res-end
                // inter-start < res-start && res-end < inter-end
                if (tmp[0] <= intervals[i][0] && intervals[i][0] <= tmp[1] && tmp[1] < intervals[i][1]) {
                    // res-start <= inter-start <= res-end && inter-end < res-end
                    list.remove(j);
                    list.add(new int[]{tmp[0], intervals[i][1]});
                    // break;
                } 
                else if (intervals[i][0] < tmp[0] && tmp[0] <= intervals[i][1] && intervals[i][1] <= tmp[1]) {
                    // inter-start < res-start && res-start <= inter-end <= res-end
                    list.remove(j);
                    list.add(new int[]{intervals[i][0], tmp[1]});
                    // break;
                }
                else if (intervals[i][0] < tmp[0] && tmp[1] < intervals[i][1]) {
                    // inter-start < res-start && res-end < inter-end
                    list.remove(j);
                    list.add(new int[]{intervals[i][0], intervals[i][1]});
                    // break;
                }
                else if (intervals[i][0] > tmp[1] || intervals[i][1] < tmp[0]) {
                    // 无需合并
                    list.add(intervals[i]);
                    // break;
                }
            }
        }
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

如果将注释中的break都去除的话，遇到输入：

intervals = [[2,3],[4,5],[6,7],[8,9],[1,10]]

输出：

[[4,5],[6,7],[8,9],[1,10]]

预期结果为：

[[1,10]]

[1, 10]只合并了[2, 3]的情况。

优秀题解

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        // [(1, 9), (2, 5), (19, 20), (10, 11), (12, 20), (0, 3), (0, 1), (0, 2)]
        // 按照一维数组第一个数进行排序
        // [(0, 3), (0, 1), (0, 2), (1, 9), (2, 5), (10, 11), (12, 20), (19, 20)]
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        // 经过排序，(第 n 个一维数组第一个数) >= (第 n+1 个一维数组第一个数)
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            // 不需要合并
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                // 合并只需比较一维数组第二个数
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/merge-intervals/solutions/203562/he-bing-qu-jian-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

14.合并区间

14.合并区间

参考链接

个人尝试（错误❌）

优秀题解