LintCode 30：Insert Interval

跟merge intervals差不多的，没什么好说的。

class Solution {public:    /**     * Insert newInterval into intervals.     * @param intervals: Sorted interval list.     * @param newInterval: new interval.     * @return: A new interval list.     **/    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {        // write your code here        if(intervals.empty()){            intervals.push_back(newInterval);            return intervals;        }        vector<Interval>::iterator p=intervals.begin();        if (newInterval.start<=p->start)            intervals.insert(p,newInterval);        else if(newInterval.start>=intervals.back().start)            intervals.push_back(newInterval);        else{            for(p=intervals.begin();p<intervals.end()-1;p++){                if(newInterval.start>=p->start&&newInterval.start<=(p+1)->start){                    intervals.insert(p+1,newInterval);                    break;                }            }        }        for(p=intervals.begin();p<intervals.end()-1;p++){            if(p->end>=(p+1)->start){                p->end=max(p->end,(p+1)->end);                intervals.erase(p+1);                p--;            }        }        return intervals;    }};