57. Insert Interval

由于insert和erase代价太大，需要移动后面所有元素。

所有空间换时间，返回新的数组ret，而不采用inplace做法。

主要以下三种情况：

1、newInterval与当前interval没有交集，则按照先后次序加入newInterval和当前interval，然后装入所有后续interval。返回ret。

2、newInterval与当前interval有交集，合并成为新的newInterval，然后处理后续interval。

3、处理完最后一个interval若仍未返回ret，说明newInterval为最后一个interval，装入ret。返回ret。

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> ret;
        if(intervals.empty())
        {
            ret.push_back(newInterval);
            return ret;
        }
            
        int i = 0;
        while(i < intervals.size())
        {
            //no overlapping
            if(newInterval.end < intervals[i].start)
            {
                ret.push_back(newInterval);
                while(i < intervals.size())
                {
                    ret.push_back(intervals[i]);
                    i ++;
                }
                return ret;
            }
            else if(newInterval.start > intervals[i].end)
                ret.push_back(intervals[i]);
            //overlapping
            else
            {
                newInterval.start = min(newInterval.start, intervals[i].start);
                newInterval.end = max(newInterval.end, intervals[i].end);
            }
            i ++;
        }
        ret.push_back(newInterval);      
        return ret;
    }
};