Saturday, December 22, 2012

[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:       }  





No comments: