【題目】

給你一個 無重疊的 ， 按照區(qū)間起始端點排序的區(qū)間列表。

在列表中插入一個新的區(qū)間，你需要確保列表中的區(qū)間仍然有序且不重疊（如果有必要的話，可以合并區(qū)間）。

示例 1：

輸入： intervals = [[1,3],[6,9]], newInterval = [2,5]
輸出： [[1,5],[6,9]]

示例 2：

輸入： intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
輸出： [[1,2],[3,10],[12,16]]
解釋： 這是因為新的區(qū)間 [4,8] 與 [3,5],[6,7],[8,10] 重疊。

示例 3：

輸入： intervals = [], newInterval = [5,7]
輸出： [[5,7]]

示例 4：

輸入： intervals = [[1,5]], newInterval = [2,3]
輸出： [[1,5]]

示例 5：

輸入： intervals = [[1,5]], newInterval = [2,7]
輸出： [[1,7]]

提示：

• 0 <= intervals.length <=
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <=
• intervals根據(jù)intervals[i][0] 按 升序 排列
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <=

【題目解析】

方法解析

1. 初始化：創(chuàng)建一個空列表merged，用于存放最終合并后的區(qū)間。

2. 遍歷區(qū)間列表：

   • 不重疊且在新區(qū)間左側(cè)：如果當(dāng)前區(qū)間的結(jié)束位置小于新區(qū)間的起始位置，將當(dāng)前區(qū)間添加到merged。
   • 重疊：如果當(dāng)前區(qū)間與新區(qū)間重疊（當(dāng)前區(qū)間的起始位置小于等于新區(qū)間的結(jié)束位置，并且當(dāng)前區(qū)間的結(jié)束位置大于等于新區(qū)間的起始位置），則將新區(qū)間更新為這兩個區(qū)間的并集。
   • 不重疊且在新區(qū)間右側(cè)：如果遇到的區(qū)間起始位置大于新區(qū)間的結(jié)束位置，說明新區(qū)間的位置已確定，將新區(qū)間添加到merged，并將剩余區(qū)間全部添加到merged。

3. 添加新區(qū)間：如果遍歷結(jié)束后新區(qū)間還沒有被添加到merged，則將其添加到最后。

def insert(intervals, newInterval):
    merged = []
    i, n = 0, len(intervals)
    
    # 遍歷并添加所有在新區(qū)間左側(cè)且不重疊的區(qū)間
    while i < n and intervals[i][1] < newInterval[0]:
        merged.append(intervals[I])
        i += 1
    
    # 合并所有與新區(qū)間重疊的區(qū)間
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
        i += 1
    merged.append(newInterval)
    
    # 添加所有在新區(qū)間右側(cè)且不重疊的區(qū)間
    while i < n:
        merged.append(intervals[I])
        i += 1
    
    return merged

執(zhí)行效率

image.png

【總結(jié)】

適用問題類型

• 區(qū)間操作問題：這類問題包括但不限于區(qū)間合并、區(qū)間插入、區(qū)間交集等，特別是那些涉及有序區(qū)間集合的問題。

解決算法：排序加貪心算法

• 算法描述：首先根據(jù)區(qū)間起始點進(jìn)行排序（如果輸入已經(jīng)有序，則可跳過此步驟），然后通過一次遍歷，貪心地選擇合并或插入?yún)^(qū)間的方式來處理重疊或相鄰的區(qū)間。

• 關(guān)鍵步驟：

  1. 遍歷區(qū)間列表，尋找插入點。
  2. 根據(jù)新區(qū)間與當(dāng)前區(qū)間的關(guān)系（不重疊、完全重疊、部分重疊）來決定是直接插入新區(qū)間、合并區(qū)間，還是保留現(xiàn)有區(qū)間。
  3. 更新結(jié)果集合。

算法特點

• 高效性：通過一次遍歷完成區(qū)間的插入和合并，避免了不必要的重復(fù)比較和計算。
• 簡潔性：算法邏輯清晰，實現(xiàn)簡潔，易于理解和維護(hù)。
• 通用性：適用于多種區(qū)間操作問題，具有良好的可擴展性。

時間復(fù)雜度與空間復(fù)雜度

• 時間復(fù)雜度：O(N log N)，主要時間開銷在于排序步驟。如果區(qū)間列表已經(jīng)有序，則時間復(fù)雜度降為O(N)，其中N是區(qū)間列表的長度。
• 空間復(fù)雜度：O(N)，需要額外空間來存儲合并后的區(qū)間列表。

實踐意義

• 廣泛應(yīng)用：這種方法不僅適用于編程競賽中的算法題目，也可用于實際開發(fā)中涉及時間段、資源分配等區(qū)間操作的場景。
• 算法思維培養(yǎng)：通過學(xué)習(xí)和實踐這種算法，可以培養(yǎng)解決問題時尋找局部最優(yōu)解以推導(dǎo)全局最優(yōu)解的思維方式。
• 性能優(yōu)化：理解和掌握貪心算法及其在區(qū)間操作問題中的應(yīng)用，有助于在面對實際問題時設(shè)計出更高效、更穩(wěn)定的解決方案。

總之，"插入?yún)^(qū)間"問題的解法提供了一種有效處理區(qū)間集合的方法，不僅解決了特定的問題場景，還拓展了我們對貪心算法在實際應(yīng)用中的理解和使用。

題目鏈接

插入?yún)^(qū)間