題目
#

leetcode 57 - Insert Interval (題目說明請點連結)

題目簡述
#

給一個無重疊的區間陣列 intervals，其中區間按起始位置排序，以及一個新的區間 newInterval。
將 newInterval 插入到 intervals 中，使得結果仍然無重疊且按起始位置排序。

範例
#

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: 插入 [2,5] 後，與 [1,3] 重疊，合併為 [1,5]。

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: 插入 [4,8] 後，與 [3,5] 和 [6,7] 重疊，合併為 [3,10]。

解題思路
#

這題要求我們將一個新的區間插入到已排序的無重疊區間陣列中。我們可以使用貪心來解決這個問題，通過遍歷現有區間，根據與新區間的關係進行不同的處理。

解法
#

貪心

創建一個結果列表和一個標記變數 inserted
遍歷現有區間，根據與新區間的關係分三種情況處理：
- 如果現有區間完全在新區間左側，直接加入結果
- 如果現有區間完全在新區間右側，先插入新區間（如果還沒插入），再加入現有區間
- 如果有重疊，擴大新區間的範圍
如果新區間還沒插入，在最後加入

步驟
#

初始化：
- 創建結果列表 res 和標記變數 inserted = false
遍歷現有區間：
- 如果 interval[1] < newInterval[0]：現有區間完全在左側，直接加入
- 如果 interval[0] > newInterval[1]：現有區間完全在右側，先插入新區間
- 否則：有重疊，擴大新區間範圍
處理新區間：
- 如果還沒插入，在最後加入新區間
返回結果：
- 將結果列表轉換為陣列並返回

例子說明
#

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

步驟	當前區間	新區間狀態	結果列表	操作說明
初始化	-	[2,5]	[]	`inserted = false`
i=0	[1,3]	[2,5]	[[1,3]]	`3 < 2` 不成立，`1 > 5` 不成立，有重疊
重疊處理	[1,3]	[1,5]	[[1,3]]	擴大新區間：`[1,5]`
i=1	[6,9]	[1,5]	[[1,3],[1,5]]	`9 < 1` 不成立，`6 > 5` 成立，插入新區間
插入完成	[6,9]	[1,5]	[[1,3],[1,5],[6,9]]	加入現有區間 [6,9]

最終結果： [[1,3],[1,5],[6,9]]

合併說明：

[2,5] 與 [1,3] 重疊，合併為 [1,5]
[1,5] 與 [6,9] 不重疊，保持原樣

完整程式碼
#

java

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        boolean inserted = false;
        List<int[]> res = new ArrayList<>();

        for (int[] interval : intervals) {
            // 如果現有區間完全在新區間左側
            if (interval[1] < newInterval[0]) {
                res.add(interval);
            } 
            // 如果現有區間完全在新區間右側
            else if (interval[0] > newInterval[1]) {
                if (!inserted) { // 直到沒有重疊塞入 newInterval
                    res.add(newInterval);
                    inserted = true;
                }
                res.add(interval);
            } 
            // 有重疊，擴大 newInterval
            else {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            }
        }

        // 如果新區間還沒插入，在最後加入
        if (!inserted) {
            res.add(newInterval);
        }

        return res.toArray(new int[res.size()][]);
    }
}