【LeetCode教學】57. Insert Interval

將新區間插入已排序的非重疊區間列表，並合併重疊區間。

題目連結：連結點此。

題目描述

給定一個不重疊區間的陣列 intervals，其中 intervals[i] = [start_i, end_i] 表示第 i 個區間的起始和結束，intervals 按 start_i 升序排列。

此外，也給定一個區間 newInterval = [start, end]，表示另一個區間的起始和結束。

將 newInterval 插入 intervals 中，使 intervals 仍依 start_i 升序排列，且 intervals 仍不包含任何重疊區間（如有必要則合併重疊區間）。

返回合併後的區間。

可以建立一個新變數並返回它，不需就地修改 intervals。

題目限制

0 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁵
intervals is sorted by start_i in ascending order.
newInterval.length == 2
0 <= start <= end <= 10⁵

解題方法

1. 先宣告一個用於儲存結果的變數output，和一個整數變數i用來記錄處理每個區間時處理到哪一個。

vector<vector<int>> output;
int i = 0;

因為 intervals 已排序，我們可以按順序處理區間，分為三部分：

2. 在新區間之前的區間（不重疊，直接加入結果）。

while (i < intervals.size() && intervals[i][1] < newInterval[0])
{
    output.push_back(intervals[i]);
    i += 1;
}

3. 與新區間重疊的區間（合併為一個區間）。

while (i < intervals.size() && intervals[i][1] >= newInterval[0] && intervals[i][0] <= newInterval[1])
{
    newInterval[0] = min(intervals[i][0], newInterval[0]); //調整新區間的開始
    newInterval[1] = max(intervals[i][1], newInterval[1]); //調整新區間的結束
    i += 1;
}
output.push_back({newInterval[0], newInterval[1]});

4. 在新區間之後的區間（不重疊，直接加入結果）。

while (i < intervals.size())
{
    output.push_back(intervals[i]);
    i += 1;
}

要特別注意的是在每個while迴圈都要加上i < intervals.size()這個判斷條件，讓如果輸入intervals為空陣列時可以不會誤動作。

完整程式碼

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {

        //1.宣告變數
        vector<vector<int>> output;
        int i = 0;  //記錄處理每個區間時處理到哪一個

        //2.先處理新區間以前的區間
        while (i < intervals.size() && intervals[i][1] < newInterval[0])
        {
            output.push_back(intervals[i]);
            i += 1;
        }

        //3.處理被新區間影響到的區間
        while (i < intervals.size() && intervals[i][1] >= newInterval[0] && intervals[i][0] <= newInterval[1])
        {
            newInterval[0] = min(intervals[i][0], newInterval[0]);  //調整新區間的開始
            newInterval[1] = max(intervals[i][1], newInterval[1]);  //調整新區間的結束
            i += 1;
        }
        output.push_back({newInterval[0], newInterval[1]});

        //4.處理新區間以後的區間
        while (i < intervals.size())
        {
            output.push_back(intervals[i]);
            i += 1;
        }

        return output;
    }
};

測試資料

首先試newInterval影響了intervals其中一個區間的情形。

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

嘗試newInterval跨越了intervals中多個區間的情形。

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

然後注意Edge case，試試看輸入為空區間的情形。

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

測試全重疊。

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

測試無重疊。

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

時間與空間複雜度

時間複雜度：O(n)，遍歷 intervals 一次。

空間複雜度：O(n)，用於儲存結果陣列。

其他相關題目

56. Merge Intervals