Google+ Followers

Sunday, April 7, 2013

[LeetCode] Merge Intervals, Solution


Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
» Solve this problem

[Thoughts]
复用一下Insert Intervals的解法即可,http://fisherlei.blogspot.com/2012/12/leetcode-insert-interval.html
创建一个新的interval集合,然后每次从旧的里面取一个interval出来,然后插入到新的集合中。

[Code]
黄色高亮部分是复用的Code.

1:       vector<Interval> merge(vector<Interval> &intervals) {            
2:            vector<Interval> result;  
3:            for(int i =0; i< intervals.size(); i++)  
4:            {  
5:                 insert(result, intervals[i]);  
6:            }  
7:            return result;  
8:       }  
9:       void insert(vector<Interval> &intervals, Interval newInterval) {        
10:            vector<Interval>::iterator it = intervals.begin();   
11:            while(it!= intervals.end())   
12:            {   
13:                 if(newInterval.end<it->start)   
14:                 {   
15:                      intervals.insert(it, newInterval);   
16:                      return;   
17:                 }   
18:                 else if(newInterval.start > it->end)   
19:                 {   
20:                      it++;   
21:                      continue;   
22:                 }   
23:                 else   
24:                 {   
25:                      newInterval.start = min(newInterval.start, it->start);   
26:                      newInterval.end = max(newInterval.end, it->end);   
27:                      it =intervals.erase(it);             
28:                 }           
29:            }   
30:            intervals.insert(intervals.end(), newInterval);    
31:       }   



Post a Comment