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. 明確時間和空間復雜度優勢，確保解法高效。

通過線性掃描法，可以快速實現插入區間問題，并展示對區間處理的全面理解，非常適合面試場景！