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）

”`