56 合并区间

一、题目

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

二、题解

思路：先排序，再合并 排序：按区间起点升序排列，这样重叠的区间就会相邻 合并：遍历排序后的区间，若当前区间起点 ≤ 上一个区间的终点，则合并；否则加入结果

import java.util.Arrays;
import java.util.LinkedList;

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

        // 1. 按照区间的起始位置进行升序排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // 2. 使用 LinkedList 存放结果，方便像栈一样操作最后一个元素
        LinkedList<int[]> merged = new LinkedList<>();

        for (int[] interval : intervals) {
            // 如果 merged 为空，或者当前区间的起始位置 > 最后一个合并区间的结束位置
            // 说明没有重叠，直接添加
            if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
                merged.add(interval);
            } else {
                // 否则说明有重叠，更新最后一个合并区间的结束位置为两者最大值
                merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
            }
        }

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

时间复杂度：O(nlog⁡n)O(n \log n)

空间复杂度：O(n)O(n)

评论