LeetCode 冥想：不重疊的區間

非重疊間隔的描述是：

給定一個間隔數組，其中間隔[i] = [start_i, end_i]，返回需要刪除以使其餘間隔不重疊的最小間隔數。

注意僅在一個點接觸的間隔不重疊。例如，[1, 2] 和 [2, 3] 不重疊。

例如：

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

或：

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

或：

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

---

對於這個問題，NeetCode 有一個很好的解決方案，從對間隔進行排序開始，就像我們在上一個問題中所做的那樣。
我們也可以初始化一個變數來追蹤刪除的數量。

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

let numRemovals = 0;

現在我們的間隔已排序，我們將遍歷每個間隔，檢查它們是否重疊。為此，我們將追蹤前一個間隔的 end，因此讓我們初始化一個 prevEnd 變量，該變量最初保存第一個間隔的結束：

let prevEnd = intervals[0][1];

注意 標題> 對於兩個間隔

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.

不重疊的情況，其中一個的開始應該嚴格大於，結束其他或其中一個的結尾應該嚴格 小於另一個的開始，如我們章節介紹中所述。 表>

在此問題中，當一個間隔的結束位置等於另一個間隔的起始位置時，它們被視為不重疊。

因此，在這裡我們可以說，如果一個間隔的開始嚴格小於另一個間隔的結束，則兩個間隔將重疊。在這種情況下，我們會將 prevEnd 更新為兩端的較小值，以便與下一個間隔重疊的機會較小。否則，我們將像以前一樣繼續：

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

最後，我們可以回傳 numRemovals:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

並且，我們的最終解決方案如下所示：

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

時間與空間複雜度

由於我們在開始時對間隔進行排序，時間複雜度將為 $O(nn n\mathrm{>l}o$n)O(n log $。我們沒有額外的資料結構，其大小會隨著輸入大小的增加而增加，因此空間複雜度為\mathrm{}($1)1

)

---

O(1)

O(1) . 接下來，我們將開始該系列的最後一章，位元操作。在那之前，祝您編碼愉快。

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