56. 合并区间

✨核心逻辑

本题采用 排序 + 贪心 的策略：

排序预处理：首先将所有区间按照 起始位置 进行升序排序。排序后，能够合并的区间必定是相邻的，这大大简化了后续的判断逻辑。
动态合并：使用一个结果列表 list 来存储当前合并好的区间。我们将排序后的第一个区间先放入结果集。
遍历与比较：从第二个区间开始遍历，每次取出当前的区间 now，以及结果集中刚刚加入的最后一个区间 last。
判断合并条件：
- 如果当前区间的起始值 now[0] 小于等于 上一个区间的结束值 last[1]，说明发生了重叠。此时只需要更新上一个区间的结束值为 max(now[1], last[1]) 即可。
- 如果不重叠，则将当前区间 now 直接添加到结果列表中。
返回结果：遍历完毕后，将 list 转换为二维数组返回。

🔥代码实现（含详细变量注释）

class Solution {
    public int[][] merge(int[][] intervals) {
        // n：记录传入的区间总数
        int n = intervals.length;
        // 安全校验：如果区间数组为空，直接返回一个空的二维数组
        if (intervals == null || intervals.length == 0) {
            return new int[0][2];
        }
        
        // 按区间的起始位置进行升序排序（使用 Lambda 表达式自定义排序规则）
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // list：动态集合，用于在合并过程中逐步存放非重叠的区间结果
        List<int[]> list = new ArrayList<>();
        
        // 预处理：将排序后的第一个区间直接放入结果集中，作为合并的基准
        list.add(intervals[0]);
        
        // i：遍历指针，从第二个区间开始向后遍历
        for (int i = 1; i < n; i++) {
            // now：当前正在处理的区间
            int[] now = intervals[i];
            
            // last：结果集合中最新放入（即当前合并链的最后一个）的区间
            int[] last = list.get(list.size() - 1);
            
            // 判断合并条件：如果当前区间的开始位置 <= 上个区间的结束位置，说明区间重叠
            if (now[0] <= last[1]) {
                // 更新上个区间的结束位置，取两个区间结束位置的较大者，完成合并
                last[1] = Math.max(now[1], last[1]);
            } else {
                // 如果没有重叠，说明当前区间是全新的独立区间，直接将其加入结果集
                list.add(now);
            }
        }
        
        // 将最终合并好的 List<int[]> 转换为符合题目要求的二维数组返回
        return list.toArray(new int[list.size()][]);
    }
}

⏱️复杂度分析
- O(N log N)，其中 N 是区间的数量。消耗主要在于对区间数组进行排序的 Arrays.sort 开销，遍历和合并过程仅需线性扫描一次 O(N)。综合复杂度为 O(N log N)。
- 空间复杂度：O(log N) 或 O(N)。排序算法通常占用 O(log N) 的栈空间（如双轴快排）；在合并时开辟了结果列表 list 用于存放区间，最坏情况下如果没有任何区间重叠，list 会占用 O(N) 的空间