LeetCode Insert Interval：區間插入與合併

題目描述

給定一組無重疊且按起始點排序的區間集合，插入一個新區間，並將有重疊的區間合併。

範例：

輸入: intervals = [[2,6],[8,10],[15,18]], newInterval = [13,16]
輸出: [[2,6],[8,10],[13,18]]

解題思路

利用原區間已排序且無重疊的特性，單次遍歷即可完成：

1. 將所有 完全在新區間左側（end < newStart）的區間直接加入結果。
2. 對於與新區間有重疊的區間，不斷更新新區間的邊界：
   newStart = min(newStart, cur.start), newEnd = max(newEnd, cur.end)。
3. 將合併後的新區間加入結果。
4. 將所有 完全在右側（start > newEnd）的區間加入結果。

參考代碼 (Python)

class Interval:
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

class Solution:
    def insert(self, intervals, newInterval):
        res = []
        i = 0
        n = len(intervals)
        # 1. 加入左側無重疊區間
        while i < n and intervals[i].end < newInterval.start:
            res.append(intervals[i])
            i += 1
        # 2. 合併重疊區間
        while i < n and intervals[i].start <= newInterval.end:
            newInterval.start = min(newInterval.start, intervals[i].start)
            newInterval.end = max(newInterval.end, intervals[i].end)
            i += 1
        res.append(newInterval)
        # 3. 加入右側剩餘區間
        while i < n:
            res.append(intervals[i])
            i += 1
        return res

複雜度分析

• 時間複雜度：O(n) —— 單次遍歷。
• 空間複雜度：O(n) —— 結果列表。