每日一题-合并区间

悠悠 2023-05-22 08:49 7阅读 0赞

今天是2020年4月16日，星期四。

### 题目描述 ###

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

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

示例 2:

输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

### 题目分析 ###

本题目的区间合并的难点在于：

*  如何确定区间之间有重叠的部分
 *  如何判断重叠部分的起始与结束

在知道了这两个关键点后，首先可以对传入的数组进行排序，排序后每个一维数组变成升序。此时拿前一个区间的右节点与当前区间的左节点进行比较，如果当前区间左节点的值 <= 前一个区间右节点的值，这说明这两个区间可以合并；新的区间的右节点值由两个区间的右节点的最大值充当。

在遍历处理区间时，每次只需要考虑与前一个区间的关系即可。

### 参考代码 ###

public class Merge {
        public int[][] merge(int[][] intervals) {
            if (intervals.length <= 0) {
                return new int[][]{};
            }
            // 先按第一个元素的升序排个序
            Arrays.sort(intervals, Comparator.comparing(o -> o[0]));
    
            int[] begin = new int[intervals.length];
            int[] end = new int[intervals.length];
    
            for (int i = 0; i < intervals.length; i++) {
                int[] current = intervals[i];
                begin[i] = current[0];
                end[i] = current[1];
            }
            // 记录需要和前面区间合并的index
            Stack<int[]> stack = new Stack<>();
            stack.push(new int[]{begin[0], end[0]});
            for (int i = 1; i < begin.length; i++) {
                // 此时两个区间应该合并
                // [1,2,8,15]
                // [3,6,10,18]
                int[] current = stack.pop();
                // 此时应该合并
                if (begin[i] <= current[1]) {
                    current[1] = Math.max(end[i], current[1]);
                    stack.push(current);
                } else {
                    stack.push(current);
                    stack.push(new int[]{begin[i], end[i]});
                }
            }
    
            List<int[]> list = new ArrayList<>();
            while (!stack.isEmpty()) {
                list.add(stack.pop());
            }
            int[][] result = new int[list.size()][2];
            int index = 0;
            for (int i = list.size() - 1; i >= 0; i--) {
                result[index] = list.get(i);
                index++;
            }
    
            return result;
        }
    }