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