這題放在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++)
        {
            #若下一個(gè)區(qū)間與上一個(gè)區(qū)間有overlap，則更新上一區(qū)間的結(jié)束點(diǎn)
            if(intervals[i].start<=ans.back().end)
                ans.back().end=max(ans.back().end,intervals[i].end);
            #否則直接講區(qū)間加入ans中
            else
                ans.push_back(intervals[i]);
        }
        return ans;
    }
};