LeetCode怎么插入区间

# LeetCode怎么插入区间

## 引言

在算法学习和面试准备中，LeetCode是一个不可或缺的平台。其中，区间类问题（如合并区间、插入区间等）是常见的题型，考察对数据结构的掌握和逻辑思维能力。本文将详细解析LeetCode中的“插入区间”问题（题目编号：57），从问题描述、解题思路到代码实现，帮助读者彻底掌握这类问题的解决方法。

---

## 问题描述

### 题目：插入区间（Insert Interval）

给定一个**无重叠**且**按照起始端点排序**的区间列表，插入一个新的区间，确保列表中的区间仍然有序且不重叠（必要时合并区间）。

**示例 1：**
```plaintext
输入：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,8]
输出：[[1,2],[3,10],[12,16]]
解释：新区间 [4,8] 与 [3,5]、[6,7]、[8,10] 重叠，合并为 [3,10]。

解题思路

关键点分析

1. 区间已排序且无重叠：原始区间列表是有序的，这简化了插入和合并的逻辑。
2. 新区间可能的位置：
   • 在某个区间之前（完全不重叠）。
   • 与一个或多个区间重叠（需要合并）。
   • 在最后一个区间之后（完全不重叠）。

解决步骤

1. 初始化结果列表：用于存储最终合并后的区间。
2. 遍历原始区间：
   • 将所有结束点小于新区间起始点的区间直接加入结果（无重叠）。
   • 合并重叠区间：找到所有与新区间重叠的区间，计算合并后的最小起始点和最大结束点。
   • 将合并后的新区间加入结果。
   • 将剩余未处理的区间加入结果。
3. 处理边界情况：如新区间在所有区间之前或之后。

代码实现

Python解法

def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)
    
    # 添加所有结束点小于新区间起始点的区间
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    
    # 合并重叠区间
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    result.append(newInterval)
    
    # 添加剩余区间
    while i < n:
        result.append(intervals[i])
        i += 1
    
    return result

复杂度分析

• 时间复杂度：O(N)，只需遍历一次区间列表。
• 空间复杂度：O(N)，存储结果列表。

边界情况与测试用例

常见边界情况

1. 新区间在所有区间之前：

   
   intervals = [[5,8]], newInterval = [1,3] → [[1,3],[5,8]]
   

2. 新区间在所有区间之后：

   
   intervals = [[1,2]], newInterval = [4,5] → [[1,2],[4,5]]
   

3. 新区间与多个区间重叠：

   
   intervals = [[1,5],[6,8]], newInterval = [3,7] → [[1,8]]
   

测试代码

# 测试示例
assert insert([[1,3],[6,9]], [2,5]) == [[1,5],[6,9]]
assert insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]) == [[1,2],[3,10],[12,16]]
assert insert([], [5,7]) == [[5,7]]
assert insert([[1,5]], [6,8]) == [[1,5],[6,8]]

扩展：相关问题

1. 合并区间（LeetCode 56）

• 题目：给定一组区间，合并所有重叠的区间。
• 解法：先排序，然后逐个合并。

2. 区间列表的交集（LeetCode 986）

• 题目：给定两个区间列表，返回它们的交集。
• 解法：双指针遍历，比较区间端点。

3. 删除被覆盖区间（LeetCode 1288）

• 题目：删除列表中所有被其他区间覆盖的区间。
• 解法：排序后统计覆盖情况。

总结

插入区间问题的核心在于正确处理重叠逻辑和高效遍历已排序区间。通过分阶段处理（无重叠、合并、剩余区间），可以清晰地将问题分解。掌握此类问题后，其他区间类题目（如合并、交集等）的解决思路也会迎刃而解。

关键步骤回顾

1. 跳过无重叠区间：直接加入结果。
2. 合并重叠区间：动态更新新区间的范围。
3. 加入剩余区间：确保结果完整性。

通过反复练习和测试边界情况，可以提升对区间问题的敏感度和代码鲁棒性。

参考资料

1. LeetCode 57. Insert Interval
2. 《算法导论》—— 分治策略与贪心算法
3. 区间类问题通用解法总结（GeeksforGeeks）

”`