LeetCode 冥想：合併間隔

讓我們從合併間隔的描述開始：

給定一個間隔數組，其中間隔[i] = [start_i, end_i]，合併所有重疊間隔，並傳回覆蓋輸入中所有間隔的非重疊間隔數組。

例如：

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

或：

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

---

我們可以先將間隔排序，以便稍後可以輕鬆比較它們：

intervals.sort((a, b) => a[0] - b[0]);

此外，我們可以初始化一個結果數組，該數組最初保存新排序間隔的第一個元素：

let result = [intervals[0]];

我們需要追蹤最後一個合併間隔的結束，將其與我們正在查看的當前間隔的開始進行比較，以檢查它們是否重疊。

注意 標題> 對於兩個不重疊的間隔，其中一個的

Note

For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

開始應該嚴格大於比結束另一個或其中一個的末端應該嚴格小於 另一個的開始，如我們章節介紹所述。 表>

如果它們不重疊，我們可以將該間隔加入結果。否則，我們需要更新“最後一個結尾”，有效地合併間隔：

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].

並且，唯一要做的就是回傳結果：

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

而且，這就是我們最終的解決方案在 TypeScript 中的樣子：

intervals.sort((a, b) => a[0] - b[0]);

時間和空間複雜度

我們是將區間排序，內建的排序功能有 $O(nn n\mathrm{>l}o$n)O(n log $時間複雜度。\; （循環是($n)n)$O(n🎜>O(n)\text{，但整體時間複雜度為}O\text{(}n$n  >l

o

g$n)O(n\; log$ ). 結果數組的大小會隨著輸入數組間隔大小的增加而增加，因此我們有

---

O

(n)n)O(n🎜> O(n) 空間複雜度。 接下來，我們將看一下「非重疊區間」一章中的最後一個問題。在那之前，祝您編碼愉快。

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