Merge Intervals

题目简介:

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

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for an interval.
     
    
   

    

     

    
    

     

       * struct Interval {
     
    
   

    

     

    
    

     

       * int start;
     
    
   

    

     

    
    

     

       * int end;
     
    
   

    

     

    
    

     

       * Interval() : start(0), end(0) {}
     
    
   

    

     

    
    

     

       * Interval(int s, int e) : start(s), end(e) {}
     
    
   

    

     

    
    

     

       * };
     
    
   

    

     

    
    

     

       */
     
    
  
 

1 先要对输入的vector进行排序,排序的代码如下,这样就可以区别vector排好序的interval之间的start是有顺序的.避免了之后判断是否合并的复杂度

  

   

    

     

    
    

     

              sort(intervals.begin(),intervals.end(),compare);
     
    
   

    

     

    
    

     

              bool compare(const Interval &inter1,const Interval         &inter2) {
     
    
   

    

     

    
    

     

                     return inter1.start<inter2.start;
     
    
   

    

     

    
    

     

              }
     
    
  
 

  

   

    

     

    
    

     

                  if (cur.end>=inter2.start) { //可以合并
     
    
   

    

     

    
    

     

                      cur.end=max(cur.end,inter2.end);
     
    
   

    

     

    
    

     

                  } else {
     
    
   

    

     

    
    

     

                      result.push_back(cur);
     
    
   

    

     

    
    

     

                      cur=inter2;
     
    
   

    

     

    
    

     

                  }
     
    
  
 

1 没有注意处理到vector最后一个interval的时候,可能会少向结果列表中加入最后一个interval

例如输入为 [[1,4],[1,4]] 我的输出直接就是[ ],也就是没有向结果列表加入任何东西啦.这就是经常遇到的末端错误啊.很多遍历的算法都可能会忽略列表末尾的逻辑处理,以后要消息啊.

文章来源: blog.csdn.net，作者：程序员历小冰，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/u012422440/article/details/44040153