原題地址：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].
給出一串區(qū)間（有序的剂买，數(shù)字從小到大），再給出另一個區(qū)間，把第二個區(qū)間和給出的那一串區(qū)間融合起來壁晒。具體的就是如果給出的第二個區(qū)間跨越了區(qū)間串里的幾個區(qū)間的話，就把那幾個被跨越的區(qū)間融合成一個葛账，如果給出的第二個區(qū)間不跨越任何區(qū)間堤如，就把這個區(qū)間單獨插入到合適的位置去。
解題思路
感覺應(yīng)該沒有什么專門的算法是用來解決這種問題的吧orz娄柳？所以完全就是把腦海里模擬的運行情況用代碼描述出來就好了，難點只在于可能會漏掉一些情況吧…比如需要插入到區(qū)間串的第一個區(qū)間之前艘绍，或者區(qū)間串為空的情況赤拒。
具體的代碼邏輯就是：
如果給出的區(qū)間串為空，直接把newInterval插入诱鞠，然后返回挎挖。
如果給出的區(qū)間串不為空，分兩種情況處理：
①newInterval能夠被直接插入航夺，不需要與其他區(qū)間融合蕉朵，即沒有和其他區(qū)間重疊的部分，代碼注釋里的case1和case2就是處理這種情況阳掐。
②newInterval有和其他區(qū)間重疊的部分始衅，這時候就要創(chuàng)建一個新的Interval對象temp，temp的start和end值通過和區(qū)間串里的值比較來確定缭保。
代碼
/**
* 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（所以確實沒有什么專門的算法吧）
