想要精通算法和SQL的成长之路 - 合并区间

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 合并区间

原题链接

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

大家可以跟这道题目做个比较：无重叠区间

思路：

1. 把数组根据左边界进行升序排序。 定义一个结果集，保存对象是一个区间，我们保证它里面的区间是不重复的，并且整体是升序的。
2. 进行数组遍历。对于当前的区间。我们就应该判断它是否需要被合并。
3. 如果左边界 > 结果集最后一个区间的右边界。那么无需合并，直接把当前区间加入到结果集。
4. 如果左边界 <= 结果集最后一个区间的右边界，即两则存在交集。那么我们需要进行数组合并，操作对象是结果集的右边界。其值为Max(当前区间的右边界，当前结果集中最后一个区间的右边界)

翻译成代码就是：

public int[][] merge(int[][] intervals) {
    if (intervals.length < 2) {
        return intervals;
    }
    // 定义结果集
    ArrayList<int[]> res = new ArrayList<>();
    // 进行区间排序,按照每个区间的左边界来升序排序
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
    // 将第一个区间加入到结果集。结果集中的区间是可以改变的。这里是一个初始化动作
    res.add(intervals[0]);
    for (int i = 1; i < intervals.length; i++) {
        // 拿到当前结果集的最后一个区间
        int[] lastInterval = res.get(res.size() - 1);
        // 当前遍历到的区间
        int[] currentInterval = intervals[i];
        // 左边界 > 结果集最后一个区间的右边界。那么无需合并，直接把当前区间加入到结果集。
        if (currentInterval[0] > lastInterval[1]) {
            res.add(currentInterval);
        } else {
            // 如果左边界 <= 结果集最后一个区间的右边界，即两则存在交集，更新结果集最后一个区间的右边界，取最大值
            lastInterval[1] = Math.max(lastInterval[1], currentInterval[1]);
        }
    }
    return res.toArray(new int[res.size()][]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25