Leetcode 57: 插入区间

Leetcode 57: 插入区间

问题描述：
给定一个非重叠的区间集合 intervals（按开始时间升序排列）和一个新的区间 newInterval，将新的区间插入到区间集合中并合并重叠的部分，最后返回结果区间集合。

适合面试的解法：线性扫描

解法特点：

• 利用区间的顺序性（已按开始时间排序），通过一次线性扫描解决问题，逻辑清晰且复杂度低。
• 核心思路：
  • 将 newInterval 插入到正确的位置，并合并所有可能的重叠区间。
• 时间复杂度 (O(n))，空间复杂度 (O(n))，非常适合面试场景。

解法思路

核心步骤：

1. 线性扫描区间数组：

   • 遍历 intervals，针对每个区间，按以下规则处理：
     • 如果当前区间在新区间之前（且不重叠），将当前区间直接加入结果。
     • 如果当前区间与新区间重叠，则调整 newInterval 为两个区间的合并结果。
     • 如果当前区间在新区间之后（且不重叠），将新区间加入结果后把剩余区间全加入结果。

2. 处理新区间：

   • 如果扫描结束时尚未添加 newInterval，将其加入结果。

3. 返回结果：

   • 返回处理后的区间集合。

代码模板：线性扫描法

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // Step 1: 遍历并处理区间
        while (i < n) {
            // 当前区间在新区间之前（不重叠）
            if (intervals[i][1] < newInterval[0]) {
                result.add(intervals[i]);
                i++;
            }
            // 当前区间与新区间重叠
            else if (intervals[i][0] <= newInterval[1]) {
                newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
                newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
                i++;
            }
            // 当前区间在新区间之后（不重叠）
            else {
                break; // 跳出，后续区间加入结果
            }
        }

        // Step 2: 添加新区间
        result.add(newInterval);

        // Step 3: 添加剩余区间
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        // Step 4: 返回结果
        return result.toArray(new int[result.size()][]);
    }
}

代码详细注释

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 初始化结果列表
        List<int[]> result = new ArrayList<>();
        int i = 0; // 当前处理区间的索引
        int n = intervals.length;

        // Step 1: 遍历区间列表
        while (i < n) {
            // Case 1: 当前区间完全在新区间之前（不重叠）
            if (intervals[i][1] < newInterval[0]) {
                result.add(intervals[i]); // 直接加入结果
                i++;
            }
            // Case 2: 当前区间与新区间重叠，需要合并
            else if (intervals[i][0] <= newInterval[1]) {
                newInterval[0] = Math.min(intervals[i][0], newInterval[0]); // 更新新区间的开始
                newInterval[1] = Math.max(intervals[i][1], newInterval[1]); // 更新新区间的结束
                i++;
            }
            // Case 3: 当前区间完全在新区间之后（不重叠）
            else {
                break; // 跳出循环，后续区间直接加入结果
            }
        }

        // Step 2: 将新区间加入结果
        result.add(newInterval);

        // Step 3: 将剩余区间加入结果
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        // Step 4: 将结果转为二维数组并返回
        return result.toArray(new int[result.size()][]);
    }
}

复杂度分析

时间复杂度：

• 线性扫描： 遍历所有区间，每个区间最多处理一次，时间复杂度为 (O(n))。

空间复杂度：

• 使用结果列表存储区间，最多 (O(n)) 的空间。

测试用例

示例 1：

输入：

intervals = [[1,3],[6,9]], newInterval = [2,5]

输出：

[[1,5],[6,9]]

解释： 新区间 [2,5] 与索引 [1,3] 重叠，合并为 [1,5]。

示例 2：

输入：

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,9]

输出：

[[1,2],[3,10],[12,16]]

解释： 新区间 [4,9] 与 [3,5],[6,7],[8,10] 重叠，合并为 [3,10]。

示例 3：

输入：

intervals = [], newInterval = [5,7]

输出：

[[5,7]]

解释： 没有初始区间，新区间直接插入。

示例 4：

输入：

intervals = [[1,5]], newInterval = [2,3]

输出：

[[1,5]]

解释： 新区间 [2,3] 被包含在已有区间 [1,5] 中，无需额外处理。

如何快速 AC（面试技巧）

1. 思路清晰：

• 利用区间的顺序性，分为三种情况处理：
  • 当前区间在 newInterval 之前；
  • 当前区间与 newInterval 重叠；
  • 当前区间在 newInterval 之后。
• 遍历结束后处理剩余区间。

2. 时间复杂度分析：

• 明确线性扫描的复杂度为 (O(n))，只需一次遍历即可完成。

3. 特殊情况处理：

• 空区间：直接将 newInterval 插入。
• 新区间完全被包含：无需额外处理。

4. 扩展能力：

• 可以进一步提及如何处理区间有额外属性（如权重或标签）时的扩展需求。
• 针对大规模区间集合的场景，可以利用二分查找优化插入点。

推荐解法：线性扫描法

适合面试的理由：

1. 思路逻辑清晰，符合区间处理的直观方式。
2. 时间复杂度 (O(n))，空间复杂度 (O(n))，为最优解法。
3. 代码简洁清晰，易于维护和扩展。

如何实现快速 AC？

1. 使用单次线性扫描，按三个情况处理区间。
2. 特殊情况（无区间或完全包含）处理到位。
3. 明确时间和空间复杂度优势，确保解法高效。

通过线性扫描法，可以快速实现插入区间问题，并展示对区间处理的全面理解，非常适合面试场景！