Skip to content

合并区间

理解题目：

题目要求合并重叠的区间，给定一组区间，如果某些区间存在重叠部分，则将它们合并成更大的区间。

代码实现：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeIntervals {
    // 合并区间
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return new int[0][];
        }

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

        List<int[]> merged = new ArrayList<>();
        for (int[] interval : intervals) {
            // 如果当前合并区间为空或当前区间起始位置大于当前合并区间的终止位置，则无重叠，直接加入合并区间
            if (merged.isEmpty() || interval[0] > merged.get(merged.size() - 1)[1]) {
                merged.add(interval);
            } else { // 否则，更新当前合并区间的终止位置为当前区间的终止位置的较大值
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}

步骤解释：

  1. 对输入的区间数组按照区间起始位置进行排序。

  2. 创建一个列表 merged 用于存储合并后的区间。

  3. 遍历排序后的区间数组：

  4. 如果当前合并区间为空或者当前区间的起始位置大于当前合并区间的终止位置，则说明当前区间与之前的区间无重叠，直接将当前区间加入合并区间列表。

  5. 否则，更新当前合并区间的终止位置为当前区间终止位置的较大值，即扩展合并区间。

  6. 将合并后的区间列表转换为二维数组并返回。

时间复杂度： 排序的时间复杂度为 O(n log n)，遍历一次区间的时间复杂度为 O(n)，因此总的时间复杂度为 O(n log n)。

空间复杂度： 除了存储排序后的区间和合并后的区间外，额外使用了常数级别的额外空间，因此空间复杂度为 O(n)。