题目：
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1:
输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]
示例 2:
输入: intervals =[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval =[4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间[4,8]与[3,5],[6,7],[8,10]重叠。
解题思路：
对于这个示例 [ [1,3], [6,9] ] ，插入的区间可分为以下几种：
1、插入区间的end小于示例第一个区间的start，如：[-1,0] ，此时应该把这个newInterval插入，然后把剩余的示例区间依次插入即可
2、插入区间在给定的两个区间的间隔处，如 [4,5]
3、插入区间有重叠，如 [2,7]
4、插入区间在给定区间的最后一个位置插入，如 [10,11]
针对1、2、3中情况容易处理，主要是第3种情况。为解决第3种情况，我们想到用双指针来记录重叠的起始位置。如设置left和right，left为开始重叠的start较小者，right为最后一个重叠的end较大者。在第3种情况中（还是以 [2,7] 为例），开始重叠时为 [1,3] ， 比较1和2，则取left为1；最后一个重叠时为 [6,9] ， 比较9和7， 则取right = 9 。
代码：
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> ans;
if(intervals.empty()) {
ans.push_back(newInterval);
return ans;
}
Interval temp;
int left,right;
int lflag = ;
int insertOk = ;
int len = intervals.size();
for(int i = ; i < len; ++i) {
if(i == && newInterval.end < intervals[i].start){ //如果newInterval在intervals的第一个之前
insertOk = ;
ans.push_back(newInterval);
}
if(insertOk) { //已经插入，把intervals的后序逐个插入
ans.push_back(intervals[i]);
continue;
}
if(newInterval.start > intervals[i].end){
ans.push_back(intervals[i]);
if(i == len - || newInterval.end < intervals[i+].start) { //判断是否是最后一个或者下一个不重叠
ans.push_back(newInterval);
insertOk = ;
}
}
else {
if(newInterval.start >= intervals[i].start && newInterval.end <= intervals[i].end) { //当前intervals包含了newInterval
ans.push_back(intervals[i]);
insertOk = ;
}
else {
if(!lflag) { //没有包含，则记录左边界
lflag = ;
left = min(newInterval.start, intervals[i].start);
}
if(newInterval.end <= intervals[i].end ) {
right = intervals[i].end; //注意这里是和下面right取值不同之处
temp.start = left;
temp.end = right;
ans.push_back(temp);
insertOk = ;
}
else {
if(i == len - || newInterval.end < intervals[i+].start) {
right = newInterval.end;
temp.start = left;
temp.end = right;
ans.push_back(temp);
insertOk = ;
} }
}
}
}
return ans;
}
};