LeetCode 冥想：插入間隔

插入間隔的描述非常解釋性：

給定一個不重疊的區間數組，其中區間[i] = [start_i, end_i] 表示第 i 個區間的開始和結束，區間按 start_i 升序排序。您也會得到一個間隔 newInterval = [start, end]，表示另一個間隔的開始和結束。

將 newInterval 插入間隔，使得間隔仍然按 start_i 升序排序，且間隔仍然沒有任何重疊間隔（如有必要，合併重疊間隔）。

返回間隔插入後。

注意您不需要就地修改間隔。您可以建立一個新數組並返回它。

例如：

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

或：

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

Explanation: Because the new interval [4, 8] overlaps with [3, 5], [6, 7], [8, 10].

---

我們可以從建立一個結果陣列開始，結果:

let result = [];

然後，遍歷所有間隔，我們需要檢查是否要將新間隔放在當前間隔之前或之後，或，它們是否重疊，因此需要合併。

正如我們在本章介紹中所看到的，兩個間隔不會重疊，如果一個的開始嚴格大於另一個的結束，或者，如果一個的結束嚴格小於比對方的開始。

當這兩種情況都為假時，它們會重疊。

首先，我們可以檢查newInterval是否在interval之前。事實上，如果我們先檢查這一點（我們可以找到放置 newInterval 的「最早」位置），我們可以立即返回新構造的結果。
這也是貪婪方法。

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)];
  }
  /* ... */  
}

但是，如果 newInterval 出現在我們正在查看的當前間隔之後，我們可以將當前間隔推入我們的結果：

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // newInterval is after interval
  else if (newInterval[0] > interval[1]) {
    result.push(interval);
  }
}

最後一個選項是當它們重疊時，在這種情況下，我們需要合併兩個間隔。我們可以再次建立 newInterval，將間隔的最小值作為新間隔的 start，將它們的最大值作為 end：

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // overlapping, create newInterval
  else {
    newInterval = [
      Math.min(newInterval[0], interval[0]),
      Math.max(newInterval[1], interval[1])
    ];
  }
}

我們的循環目前如下：

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)] 

  // newInterval is after interval
  } else if (newInterval[0] > interval[1]) {
    result.push(interval);

  // overlapping, create newInterval
  } else {
    newInterval = [Math.min(newInterval[0], interval[0]), Math.max(newInterval[1], interval[1])];
  }
}

我們還需要推送我們創建的最新的 newInterval。最後，我們可以回傳結果：

function insert(intervals: number[][], newInterval: number[]): number[][] {
  /* ... */
  result.push(newInterval);
  return result;
}

最後，解如下：

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

時間和空間複雜度

時間複雜度為 $O(n))$O(n🎜> O(n)$O()$n)O(n🎜>

---

O(n) 我們保留一個結果數組，它的大小會隨著間隔長度的增加而增加。 接下來，我們將了解合併間隔。在那之前，祝您編碼愉快。

以上是LeetCode 冥想：插入間隔的詳細內容。更多資訊請關注PHP中文網其他相關文章！