24. 合并区间：给定一组区间，合并所有重叠的区间

合并区间问题是一个经典的算法问题，通常要求我们将给定的一组区间合并，确保没有重叠的区间。解决这个问题的关键在于如何正确地排序和合并区间。

1. 问题描述

给定一组区间（每个区间表示为一个由两个整数组成的数组，例如 [start, end]），合并所有重叠的区间，并返回一个不重叠的区间列表。

2. 算法思路

合并区间的步骤如下：

1. 排序：首先将所有区间按照起始值 start 进行排序。

2. 遍历并合并

   ：从第一个区间开始，逐个遍历排序后的区间列表：

   • 如果当前区间与上一个合并后的区间有重叠（即当前区间的起始值小于或等于上一个区间的结束值），那么就将当前区间与上一个区间合并。
   • 如果当前区间与上一个区间没有重叠，则将上一个合并后的区间添加到结果列表中，并将当前区间作为新的待合并区间。

3. 处理最后一个区间：由于最后一个区间在遍历结束后不会被自动添加到结果列表中，需要手动添加。

3. 代码实现

下面是用 Java 实现的合并区间的代码：

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

public class MergeIntervals {

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][0];
        }

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

        // 用来存放合并后的区间列表
        List<int[]> merged = new ArrayList<>();

        // 初始化第一个区间为当前区间
        int[] currentInterval = intervals[0];
        merged.add(currentInterval);

        // 遍历区间列表并合并重叠区间
        for (int[] interval : intervals) {
            int currentStart = currentInterval[0];
            int currentEnd = currentInterval[1];
            int nextStart = interval[0];
            int nextEnd = interval[1];

            if (currentEnd >= nextStart) { // 有重叠
                // 合并区间
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            } else { // 无重叠
                // 将当前区间添加到结果列表
                currentInterval = interval;
                merged.add(currentInterval);
            }
        }

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

    public static void main(String[] args) {
        MergeIntervals solution = new MergeIntervals();

        int[][] intervals = {
            {1, 3},
            {2, 6},
            {8, 10},
            {15, 18}
        };

        int[][] mergedIntervals = solution.merge(intervals);

        System.out.println("Merged intervals:");
        for (int[] interval : mergedIntervals) {
            System.out.println(Arrays.toString(interval));
        }
    }
}

4. 示例解释

假设输入的区间列表为：[[1, 3], [2, 6], [8, 10], [15, 18]]

1. 排序：
   • 排序后的区间列表为：[[1, 3], [2, 6], [8, 10], [15, 18]]（起始值已经按从小到大排列）。
2. 合并：
   • 第一个区间 [1, 3] 和第二个区间 [2, 6] 重叠，合并为 [1, 6]。
   • [1, 6] 和 [8, 10] 不重叠，所以 [1, 6] 加入结果列表。
   • [8, 10] 和 [15, 18] 不重叠，所以 [8, 10] 加入结果列表。
   • [15, 18] 加入结果列表。
3. 输出结果：
   • 合并后的区间列表为：[[1, 6], [8, 10], [15, 18]]。

5. 复杂度分析

• 时间复杂度：O(n log n)，主要消耗在排序步骤，排序的时间复杂度是 O(n log n)，遍历区间的时间复杂度是 O(n)。
• 空间复杂度：O(n)，用于存储合并后的区间列表。

6. 总结

通过排序和遍历的方式，可以有效地合并所有重叠的区间。该方法在时间复杂度和空间复杂度上都表现良好，适用于处理大规模的区间合并问题。