Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

1. 插入interval的end比第一个interval的start要小
2. 插入interval的start比最后一个interval的end要大
3. 原interval序列长度为0或1
4. 插入interval的start或end在前一个interval的end之后，在后一个interval的start之前
5. 插入interval的start和end都在前一个interval的end后和后一个interval的start前

PS：开始也是没想到这么多情况。。于是修修补补代码非常乱，等有机空整理下估计能好看些。

``````
class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
if(intervals.size() == 0)
{
intervals.push_back(newInterval);
return intervals;
}
else if(intervals.size() == 1)
{
if(newInterval.end < intervals[0].start) intervals.insert(intervals.begin(), newInterval);
else if(newInterval.start <= intervals[0].end && newInterval.end >= intervals[0].start)
{
intervals[0].start = min(newInterval.start, intervals[0].start);
intervals[0].end = max(newInterval.end, intervals[0].end);
}
else if(newInterval.start > intervals[0].end) intervals.push_back(newInterval);
return intervals;
}

int delS = 0, delE = 0;
int first = 0, last = intervals.size() - 1, half;

while(last - first > 1)
{
half = (first + last) / 2;
if(newInterval.start > intervals[half].end) first = half;
else if(newInterval.start < intervals[half].start) last = half;
else
{
delS = half;
break;
}
}

if(last - first <= 1)
{
if(newInterval.start > intervals[last].end){ intervals.push_back(newInterval);         return intervals; }
else if(newInterval.start > intervals[first].end)
{
if(newInterval.end < intervals[last].start)
{
intervals.insert(intervals.begin() + last, newInterval);
return intervals;
}
delS = last;
}
else if(newInterval.start >= intervals[last].start) delS = first;
else
{
delS = first;
if(newInterval.end < intervals[first].start)
{
intervals.insert(intervals.begin() + delS, newInterval);
return intervals;
}
}
intervals[delS].start = min(intervals[delS].start, newInterval.start);
}

first = delS, last = intervals.size() - 1;
while(last - first > 1)
{
half = (first + last) / 2;
if(newInterval.end < intervals[half].start) last = half;
else if(newInterval.end > intervals[half].end) first = half;
else { delE = half; break; }
}

if(last - first <= 1)
{
if(newInterval.end < intervals[last].start) delE = first;
else delE = last;
intervals[delS].end = max(intervals[delE].end, newInterval.end);
}
else intervals[delS].end = intervals[delE].end;

intervals.erase(intervals.begin() + (delS + 1), intervals.begin() + (delE + 1));

return intervals;
}
};
``````