这题放在56题之后是有道理的，和56题方法相同，在此不再赘述。

class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> ans;
        if(intervals.empty())
        {
            ans.push_back(newInterval);
            return ans;
        }
        int k=0,n=intervals.size();
        while(k<n&&intervals[k].start<newInterval.start)
            k++;
        intervals.insert(intervals.begin()+k,newInterval);
        ans.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++)
        {
            #若下一个区间与上一个区间有overlap，则更新上一区间的结束点
            if(intervals[i].start<=ans.back().end)
                ans.back().end=max(ans.back().end,intervals[i].end);
            #否则直接讲区间加入ans中
            else
                ans.push_back(intervals[i]);
        }
        return ans;
    }
};