合并区间

约 1458 字大约 5 分钟

2025-02-23

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 <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

按起点升序，饿汉

思路：

把所有区间按照起点升序排序。
遍历所有区间，每次比较当前区间的起点和上一个区间的终点，

若不重叠，则先把当前区间加入结果列表（以后可能还会去掉它），这是一个贪心策略，默认它是合规的。先相信，再质疑。饿汉模式。还有一个原因是对最后一个区间，它后面没有区间，所以只要它和前面的不重叠，就一定是合规的。
若重叠，则合并这两个区间，生成一个新区间，用它冲掉结果列表中的上一个区间。

最终结果列表中的所有区间都是不重叠的。

细节：

判空
不管是否重叠，每次操作完都要更新终点以便下次比较。不同的是，若重叠，则终点是这两个重叠区间的终点的最大值；若不重叠，则终点是当前区间的终点。
列表转二维数组：list.toArray(new int[list.size()][])

思想：

按起点升序排序的好处是，如果当前区间的起点大于上一个区间的终点，则后面的区间都不用扫描了，全都和上一个区间不相交。如果不这样排序，则需要遍历后面所有的区间，检查这些区间的起点是否小于上一个区间的终点。本质上还是”赛马问题“。
不需要按照终点降序排序了，按终点降序的好处是，该区间后面的第一个与之不相交的区间就是这一类区间中最长的区间，即它能够区分重叠中的覆盖与非覆盖。但是我们不需要区分覆盖与非覆盖，处理策略都一样，即只要当前区间和前一个区间有重叠，就要执行合并操作。

class Solution {
    public int[][] merge(int[][] intervals) {
        // 如果输入数组为空，则直接返回空数组
        if (intervals.length == 0) {
            return new int[0][2];
        }
        
        // 使用 Lambda 表达式根据每个区间的起始位置进行升序排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // 用来存放合并后的区间
        List<int[]> ans = new ArrayList<>();

        // 初始化第一个区间的结束时间
        int e1 = intervals[0][1];
        
        // 遍历所有区间
        for (int[] interval : intervals) {
            // 当前区间的开始和结束时间
            int s2 = interval[0];
            int e2 = interval[1];
            
            // 如果当前区间的开始时间小于等于上一个区间的结束时间，说明有重叠。
            if (s2 <= e1) {
                // 合并区间，更新结束时间为两个区间结束时间的最大值
                e1 = Math.max(e2, e1);
                int s1 = ans.get(ans.size()-1)[0];
                
                // 移除结果列表中的最后一个区间（因为需要更新其结束时间）
                ans.remove(ans.size() - 1);
                // 添加更新后的合并区间
                ans.add(new int[] { s1, e1 });
            } else {
                // 如果没有重叠，则直接添加当前区间到结果列表
                ans.add(new int[] { s2, e2 });
                // 更新e1为当前区间的结束时间
                e1 = e2;
            }
        }

        // 将List转换为二维数组并返回
        return ans.toArray(new int[ans.size()][]);
    }
}

时间复杂度：排序需要 O(NlogN)，遍历需要 O(N)
空间复杂度：排序需要 O(logN)，存储答案需要 O(N)

按起点升序，懒汉，好

思路：

把所有区间按照起点升序排序。
遍历所有区间，每次比较当前区间的起点和上一个区间的终点，

若不重叠，则先把前一个区间加入结果列表。懒汉模式。
若重叠，则更新“比较终点”为这两个重叠区间的终点的最大值。先不加入结果列表，因为后面可能还有重叠的区间。

最后要把最后一个区间加入结果列表。

import java.util.*;

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

        // 使用Lambda表达式先按起点升序，再按终点降序排序。其实这个解法只对起点升序排序也可以。
        Arrays.sort(intervals, (a, b) -> {
            return a[0] != b[0] ? a[0] - b[0] : b[1] - a[1];
        });

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

        // 初始化第一个区间的起始和结束时间
        int s1 = intervals[0][0];
        int e1 = intervals[0][1];

        // 遍历所有区间
        for (int[] interval : intervals) {
            // 当前区间的开始和结束时间
            int s2 = interval[0];
            int e2 = interval[1];

            // 如果当前区间的开始时间小于等于上一个区间的结束时间，说明有重叠。
            if (s2 <= e1) {
                // 合并区间，更新结束时间为两个区间结束时间的最大值
                e1 = Math.max(e2, e1);
            } else {
                // 如果没有重叠，则将上一个区间添加到结果列表
                ans.add(new int[] { s1, e1 });
                // 更新s1和e1为当前区间的起始和结束时间
                s1 = s2;
                e1 = e2;
            }
        }

        // 将最后一个区间加入结果列表
        ans.add(new int[] { s1, e1 });

        // 将List转换为二维数组并返回
        return ans.toArray(new int[ans.size()][]);
    }
}