[LeetCode] Insert Interval 解题报告

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].

» Solve this problem

[解题思路]
没什么好说的，遍历已有vector，如果当前interval小于newinterval，插入当前；如果当前interval大于newInterval，则插入newInterval及当前；如果两者重叠，merge以后插入新的interval。
实现中之所以重新new了一个vector来存放结果的原因，是不愿意破坏传入参数。
在原有的vector上面直接修改的话，唯一的区别就是，一旦发现当前interval大于newInterval，就应该return了。


[Code]

1:   vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      vector<Interval> result;  
5:      result.push_back(newInterval);  
6:      for(int i=0; i< intervals.size(); i++)  
7:      {  
8:        Interval newInt = result.back();  
9:        result.pop_back();  
10:        Interval* cur = &intervals[i];  
11:        if(cur->end < newInt.start)  
12:        {  
13:          result.push_back(*cur);  
14:          result.push_back(newInt);          
15:        }        
16:        else if(cur->start > newInt.end)  
17:        {  
18:          result.push_back(newInt);  
19:          result.push_back(*cur);          
20:        }  
21:        else  
22:        {          
23:          newInt.start = min(cur->start, newInt.start);  
24:          newInt.end = max(cur->end, newInt.end);  
25:          result.push_back(newInt);  
26:        }  
27:      }  
28:      return result;  
29:    }  

[发散]
以前换组的时候，面过这道题，但是出题的人，添加了一个附属条件，这些interval是在一个圆环上。比如当环是[1, 255]时，如果两个Interval分别是[1,234], [222, 4], Merge最后的结果是[1,4]。这个条件完全是个干扰，因为如果真的在逻辑中考虑环的话，非常麻烦，而且在环上做循环合并的话，无法判断何时该终止循环。当时我的解法就是，如果第一个是跨越0点的话（比如[234,7]），把它拆分成两个interval（[234, 255],[1,7]）， 然后把[1,7]插到队头，[234,255]插到队尾。 从[1,7]开始往后合并，合并完成后，再检查对头及队尾，需要的话，再合并一次即可。

Update: 03/14/3013. Refactor code
第一版code因为不了解c++，不知道怎么在iterate vector的过程中做删除，所以引入了多余的空间。后来搜了一下，删除不能再for loop里面做，而要放在while loop中，通过Line 19 返回删除元素下一个元素。

1:       vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {            
2:            vector<Interval>::iterator it = intervals.begin();  
3:            while(it!= intervals.end())  
4:            {  
5:                 if(newInterval.end<it->start)  
6:                 {  
7:                      intervals.insert(it, newInterval);  
8:                      return intervals;  
9:                 }  
10:                 else if(newInterval.start > it->end)  
11:                 {  
12:                      it++;  
13:                      continue;  
14:                 }  
15:                 else  
16:                 {  
17:                      newInterval.start = min(newInterval.start, it->start);  
18:                      newInterval.end = max(newInterval.end, it->end);  
19:                      it =intervals.erase(it);                      
20:                 }                 
21:            }  
22:            intervals.insert(intervals.end(), newInterval);            
23:            return intervals;            
24:       }