图解LeetCode——56. 合并区间

一、题目

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

二、示例

2.1> 示例 1：

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

2.2> 示例 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

三、解题思路

根据题目要求，我们要合并所有重叠的区间，那么我们为了便于操作，首先可以将数组intervals进行排序，即：根据每个区间中的左区间来进行排序操作。那么在这样排完序的数组intervals中，排在前面元素的开始区间一定小于或者等于排在后面元素的开始区间。

排序完毕之后，我们就可以开始执行重叠区间的合并操作了。首先，我们创建两个指针，分别为：head和tail，用于表示当前区间的首位值。然后，创建一个集合result，用于存储合并重叠区间后的最新区间。最后，我们遍历数组intervals，对于合并操作，规则如下所示：

【规则1】如果满足head == intervals[i][0] 或者 tail > intervals[i][0] ，并且满足 tail < intervals[i][1] ，那么我们就更新tail指针，即：tail = intervals[i][1];
【规则2】否则，说明区间并未发生重叠，则将head和tail组成区间 [head, tail] ，然后存储到result集合中。然后，更新head指针和tail指针。即：head = intervals[i][0]，tail = intervals[i][1];

如上就是这道题的解题思路了，为了便于理解，我们以输入为intervals = [[1,3],[7,8],[2,6],[10,11]]为例，看一下具体的执行操作是怎么样的。请见下图所示：

四、代码实现

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> result = new ArrayList<>();
        // Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a1, int[] a2) {
                return a1[0] - a2[0];
            }
        });
        int head = intervals[0][0], tail = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (head == intervals[i][0] || tail >= intervals[i][0]) {
                if (tail < intervals[i][1]) tail = intervals[i][1];
            } else {
                result.add(new int[]{head, tail});
                head = intervals[i][0];
                tail = intervals[i][1];
            }
        }
        result.add(new int[]{head, tail});
        return result.toArray(new int[result.size()][]);
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞 & 分享。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」