57. Insert Interval

題目網址：https://leetcode.cn/problems/insert-interval/

題意：給一無重疊的 interval array intervals, 且 intervals 已根據 intervals[i][0] 做升序排列。

今插入一區間 newInterval, 必須確保插入後 intervals 仍升序排列且不重疊 (如果有必要的話, 可以合併區間)

Solution：

想法：先將 newInterval 插入 intervals 中的正確位置, 然後再利用 56. Merge Intervals 進行 merge

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        auto it = intervals.begin();

        // 根據 start 將 newInterval 插入到 intervals 中
        while (it != intervals.end() && newInterval[0] > (*it)[0]) {
            ++it;
        }

        intervals.insert(it, newInterval);
        vector<vector<int>> res{intervals[0]};

        for (int i = 1; i < intervals.size(); ++i) {
            // 取出前一個 interval 的 end
            const int lastEnd = res.back()[1];

            // 若 interval[i].start <= interval[i-1].end, 則重設新的 end(合併)
            if (intervals[i][0] <= lastEnd) {
                res.back()[1] = max(lastEnd, intervals[i][1]);
            } else {
                res.emplace_back(intervals[i]);
            }
        }

        return res;
    }
};

• time：$O(n)$ ➔ 遍歷 intervals
• space：$O(n)$ ➔ res