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

 

Show Tags

   

 

---

　　这题其实想好思路很好解决，对于框，如果下个框开始在 其中间，则连在一起，否则单独为一个，这需要按start 排序便可以了，因为类中写自定义比较函数比较麻烦，所以一次写了好几个。

1. 按start 排序
2. 初始化变量curstart,curend,记录当前窗的位置。
3. 与下个窗比较，如果其start < curend，更新 curend。
4. 否则加入ret，并跟新curstart,curend
5. 遍历结束，加入最后的窗。

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 using namespace std; 5  6 /** 7  * Definition for an interval. 8  */ 9  struct Interval {10     int start;11     int end;12     Interval() : start(0), end(0) {}13     Interval(int s, int e) : start(s), end(e) {}14 };15 16 class Solution {17 public:18     vector
          
            merge(vector
           
             &intervals) {19         sort(intervals.begin(),intervals.end(),\20              [] (Interval i1,Interval i2)\21              {
     return i1.start
            
              ret;38 if(intervals.size()<1) return ret;39 int curStart=intervals[0].start,curEnd=intervals[0].end;40 for(int i=1;i
             
              =intervals[i].start){42 if(intervals[i].end>curEnd) curEnd=intervals[i].end;43 continue;44 }45 ret.push_back(Interval(curStart,curEnd));46 curStart = intervals[i].start;47 curEnd = intervals[i].end;48 }49 ret.push_back(Interval(curStart,curEnd));50 return ret;51 }52 53 static bool help_fun(Interval i1,Interval i2)54 {55 return i1.start
              
                intervals={Interval(8,10),\62 Interval(2,6),\63 Interval(1,3),\64 Interval(15,18)};65 Solution sol;66 vector
               
                 ret = sol.merge(intervals);67 68 for(int i=0;i