insert.cpp

#include <vector>

using namespace std;

class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        vector<vector<int>> res;
        if (intervals.empty()) return res;
            // intervals已排序，所以我们不用再排序了
            // 直接遍历这个排序好的数组，插入即可
            for (int i = 0; i < intervals.size(); i++)
        {
            if (i + 1 > intervals.size()) break;
            if (intervals[i][0] <= newInterval[0] && intervals[i + 1][0] >= newInterval[0])
            {
                intervals.insert(intervals.begin() + i + 1,newInterval);
                break;    
            }
        }

        // 随后继续进行merge操作
        res.push_back(intervals[0]);
        for (int i = 1;i < intervals.size();i++)
        {
            if (res.back()[1] >= intervals[i][0])
            {
                res.back()[1] = max(res.back()[1],intervals[i][1]);
            }
            else res.push_back(intervals[i]);
        }

        return res;
    }

private:
    template<typename T>
    T max(T num1,T num2)
    {
        if (num1 > num2) return num1;
        else return num2;
    }
};