56. 合并区间

题目：合并区间

描述：

给定一个区间集合 intervals，每个区间用 [starti, endi] 表示。需要合并所有 重叠 的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

---

示例：

示例 1:

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

示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 相互重叠, 合并为 [1,5].

---

解题思路

核心思想：

• 重叠的两个区间 [a, b] 和 [c, d] 的条件 是 c <= b，即后一个区间的起点小于等于前一个区间的终点。
• 合并区间的规则：
  • 如果两个区间重叠，则将它们合并为 [min(a, c), max(b, d)]。

步骤：

1. 排序：

   • 首先对所有区间按起点 start 进行排序。这样可以确保合并的顺序是从左到右的。

2. 遍历合并：

   • 初始化一个结果列表 merged。
   • 遍历排序后的区间：
     • 如果结果列表为空，或者当前区间的起点 start 大于结果列表最后一个区间的终点 end，直接将当前区间加入结果列表。
     • 否则，说明当前区间与结果列表最后一个区间有重叠，更新最后一个区间的终点为两个区间终点的最大值。

3. 返回结果。

---

代码实现

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取区间的数量
        int n = scanner.nextInt();
        int[][] intervals = new int[n][2];

        // 读取每个区间的起点和终点
        for (int i = 0; i < n; i++) {
            intervals[i][0] = scanner.nextInt();
            intervals[i][1] = scanner.nextInt();
        }

        Solution solution = new Solution();
        int[][] result = solution.merge(intervals);

        // 输出合并后的区间
        System.out.print("[");
        for (int i = 0; i < result.length; i++) {
            System.out.print("[" + result[i][0] + "," + result[i][1] + "]");
            if (i < result.length - 1) System.out.print(",");
        }
        System.out.println("]");

        scanner.close();
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        // 1. 对区间按起点进行排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> merged = new ArrayList<>(); // 结果列表

        for (int[] interval : intervals) {
            // 如果结果列表为空，或者当前区间与结果列表最后一个区间无重叠
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                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()][]);
    }
}

---

代码解析

示例：intervals = [[1,3],[2,6],[8,10],[15,18]]

1. 排序：

   • 按起点排序后，intervals = [[1,3],[2,6],[8,10],[15,18]]（排序后未变化）。

2. 初始化结果列表：

   • merged = []。

3. 遍历合并：

   • 第 1 个区间 [1,3]：

     • merged 为空，直接加入。
     • merged = [[1,3]]。

   • 第 2 个区间 [2,6]：

     • 当前区间起点 2 小于等于 merged 中最后一个区间的终点 3，说明有重叠。
     • 合并为 [1,6]。
     • merged = [[1,6]]。

   • 第 3 个区间 [8,10]：

     • 当前区间起点 8 大于 merged 中最后一个区间的终点 6，说明无重叠。
     • 直接加入结果列表。
     • merged = [[1,6],[8,10]]。

   • 第 4 个区间 [15,18]：

     • 当前区间起点 15 大于 merged 中最后一个区间的终点 10，说明无重叠。
     • 直接加入结果列表。
     • merged = [[1,6],[8,10],[15,18]]。

4. 返回结果：

   • 返回 [[1,6],[8,10],[15,18]]。

---

时间复杂度

1. 排序：O(n log n)，n 是区间的数量。
2. 遍历区间：O(n)，合并操作中只需要遍历一次区间列表。

总时间复杂度：O(n log n)。

---

空间复杂度

1. 存储结果列表：需要额外的 O(n) 空间存储合并后的区间。
2. 排序：如果使用原地排序，空间复杂度为 O(1)，否则为 O(n)。

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

---

总结

1. 核心思想：

   • 排序后，合并重叠区间的过程可以通过遍历和判断终点是否重叠来高效完成。
   • 通过不断更新结果列表中最后一个区间的终点来实现合并操作。

2. 适用场景：

   • 适合解决需要处理区间合并的各种问题，比如时间段的安排、区间覆盖等。