原题地址：https://leetcode.com/problems/insert-interval/description/
题目描述
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].
给出一串区间（有序的，数字从小到大），再给出另一个区间，把第二个区间和给出的那一串区间融合起来。具体的就是如果给出的第二个区间跨越了区间串里的几个区间的话，就把那几个被跨越的区间融合成一个，如果给出的第二个区间不跨越任何区间，就把这个区间单独插入到合适的位置去。
解题思路
感觉应该没有什么专门的算法是用来解决这种问题的吧orz？所以完全就是把脑海里模拟的运行情况用代码描述出来就好了，难点只在于可能会漏掉一些情况吧…比如需要插入到区间串的第一个区间之前，或者区间串为空的情况。
具体的代码逻辑就是：
如果给出的区间串为空，直接把newInterval插入，然后返回。
如果给出的区间串不为空，分两种情况处理：
①newInterval能够被直接插入，不需要与其他区间融合，即没有和其他区间重叠的部分，代码注释里的case1和case2就是处理这种情况。
②newInterval有和其他区间重叠的部分，这时候就要创建一个新的Interval对象temp，temp的start和end值通过和区间串里的值比较来确定。
代码
/**
* 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> vec;
//if the intervals is empty,insert the newInterval directly
if(intervals.empty()){
vec.push_back(newInterval);
return vec;
}
bool done=false; //indicate whether the given newInterval has been inserted
for(int i=0; i<intervals.size();){
if(done){
vec.push_back(intervals[i]);
i++;
}else if(newInterval.end<intervals[i].start){ //case 1
vec.push_back(newInterval);
done=true;
} else if(newInterval.start>intervals[i].end){
vec.push_back(intervals[i]);
if(i==intervals.size()-1){ //case 2
vec.push_back(newInterval);
done=true;
}
i++;
}else{ //case 3
Interval temp;
if(newInterval.start<intervals[i].start){
temp.start=newInterval.start;
}else{
temp.start=intervals[i].start;
}
int j;
for(j = i;j<intervals.size()-1; j++){
if(newInterval.end <= intervals[j].end && newInterval.end>=intervals[j].start){
temp.end=intervals[j].end;
done=true;
vec.push_back(temp);
i=j+1;
break;
}else if(newInterval.end>intervals[j].end&& newInterval.end <intervals[j+1].start){
temp.end = newInterval.end;
done=true;
vec.push_back(temp);
i=j+1;
break;
}
}
if(!done){
int k = intervals.size()-1;
if(newInterval.end<=intervals[k].end&&newInterval.end>=intervals[k].start ){
temp.end = intervals[k].end;
}else if(newInterval.end > intervals[k].end){
temp.end=newInterval.end;
}
vec.push_back(temp);
break;
}
}
}
return vec;
}
};
虽然代码很丑但是时间倒是出乎意料地击败了蛮多人…是最好的一次了23333（所以确实没有什么专门的算法吧）
