想要精通算法和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 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()][]);
}