題目： LeetCode - 57. Insert Interval

題目說明

給一個代表區間的陣列，及一個要插入陣列的區間，插入後需要將重疊的部分合併。

解題思路

由於陣列已經依照起始點的位置排序過，所以只需要將區間插入到正確的位置，接著利用 LeetCode - 56 的作法來將重疊的部分合併即可。詳細作法可參考本篇文章：LeetCode - 56 解題紀錄。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
    {
        auto iter = intervals.begin();
        while(iter != intervals.end() && iter->at(0) < newInterval[0]) ++iter;
        intervals.insert(iter, newInterval);
        vector<vector<int>> res;
        for(auto& interval : intervals)
        {
            if(res.empty() || interval[0] > res.back()[1]) res.emplace_back(interval);
            else res.back()[1] = max(res.back()[1], interval[1]);
        }
        return res;
    }
};