🔗 合并区间

题目来源：56. 合并区间 – 力扣（LeetCode）

---

📌 题目描述

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

• 重叠定义：两个区间 [a, b] 和 [c, d] 重叠，当且仅当 b >= c 且 d >= a（即有交集）。
• 特别地，[1,4] 和 [4,5] 被视为重叠（端点相接）。

---

✅ 示例解析

示例 1：

• 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
• 输出：[[1,6],[8,10],[15,18]]
• 解释：
  • [1,3] 与 [2,6] 重叠 → 合并为 [1,6]
  • [8,10] 和 [15,18] 无重叠，保留原样。

示例 2：

• 输入：intervals = [[1,4],[4,5]]
• 输出：[[1,5]]
• 解释：两个区间端点相接，合并为 [1,5]。

示例 3：

• 输入：intervals = [[1,4],[0,4]]
• 输出：[[0,4]]
• 解释：[0,4] 完全覆盖 [1,4]，合并后为 [0,4]。

---

⚠️ 提示

• 1 <= intervals.length <= 10⁴
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10⁴

---

💡 解法：排序 + 贪心合并 —— O(n log n) 时间

class Solution {
    public int[][] merge(int[][] intervals) {
        int[][] ans = new int[intervals.length][2];
        Arrays.sort(intervals, (p1, p2) -> p1[0] - p2[0]);
        int index = -1;
        for (int[] p : intervals) {
            if (index == -1 || p[0] > ans[index][1]) {
                ans[++index] = p;
            } else {
                ans[index][1] = Math.max(ans[index][1], p[1]);
            }
        }
        return Arrays.copyOf(ans, index + 1);
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n log n)
  • 排序：O(n log n)（主导项）
  • 遍历合并：O(n)
  • 总体时间由排序决定。
• 空间复杂度：O(1)（不计返回数组）
  • 使用固定大小的辅助数组 ans（最多存储 n 个区间）
  • 排序空间取决于底层实现（如快速排序为 O(log n)）
  • 通常认为额外空间为常数或对数级。

---

🧩 解题思路

1. 核心思想：排序 + 贪心合并
   • 先按区间的起始位置升序排序。
   • 遍历排序后的区间，维护一个当前合并区间，若与下一个区间重叠则合并，否则加入结果。
2. 为什么要排序？
   • 排序后，所有可能重叠的区间都会相邻出现。
   • 只需判断当前区间与前一个合并区间的结束位置关系即可。
3. 合并逻辑：
   • 使用 ans 数组存储合并结果，index 指向最后一个已合并区间的索引。
   • 遍历每个区间 p = [start, end]：
     • 情况 1：若当前结果为空（index == -1）或 p[0] > ans[index][1]（无重叠）
       → 将 p 作为新区间加入：ans[++index] = p
     • 情况 2：若 p[0] <= ans[index][1]（有重叠）
       → 合并：更新当前区间的右端点为 max(ans[index][1], p[1])
4. 关键点：端点相接也算重叠
   条件 p[0] > ans[index][1] 表示“无重叠”，反之（<=）即为重叠，包含端点相接的情况。
5. 结果截取：
   • ans 数组初始大小为 intervals.length，但实际合并后数量可能更少。
   • 使用 Arrays.copyOf(ans, index + 1) 返回有效部分。
6. 举例说明：
   对 intervals = [[1,3],[2,6],[8,10],[15,18]]：
   • 排序后不变
   • p=[1,3]：index=-1 → 加入，ans[0]=[1,3], index=0
   • p=[2,6]：2 <= 3 → 合并，ans[0]=[1,6]
   • p=[8,10]：8 > 6 → 无重叠，ans[1]=[8,10], index=1
   • p=[15,18]：15 > 10 → 无重叠，ans[2]=[15,18], index=2
   • 返回 ans[0..2]