[LeetCode] Merge Intervals 排序sort

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 排序便可以了，因为类中写自定义比较函数比较麻烦，所以一次写了好几个。

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

 #include <iostream>

 #include <vector>

 #include <algorithm>

 using namespace std;

 /**

  * Definition for an interval.

  */

  struct Interval {

     int start;

     int end;

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

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

 };

 class Solution {

 public:

     vector<Interval> merge(vector<Interval> &intervals) {

         sort(intervals.begin(),intervals.end(),\

              [] (Interval i1,Interval i2)\

              {return i1.start<i2.start; });

 ///        sort(intervals.begin(),intervals.end(),help_fun);

 /**        struct my_cmp{

             bool operator ()(Interval i1,Interval i2){

                 return i1.start<i2.start;

             }

         }my_cmp1;

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

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

 */

 //        for(int i=0;i<intervals.size();i++){

 //            cout<<intervals[i].start<<" "<<intervals[i].end<<endl;

 //        }

         vector<Interval> ret;

         if(intervals.size()<)  return ret;

         int curStart=intervals[].start,curEnd=intervals[].end;

         for(int i=;i<intervals.size();i++){

             if(curEnd>=intervals[i].start){

                 if(intervals[i].end>curEnd) curEnd=intervals[i].end;

                 continue;

             }

             ret.push_back(Interval(curStart,curEnd));

             curStart = intervals[i].start;

             curEnd = intervals[i].end;

         }

         ret.push_back(Interval(curStart,curEnd));

         return ret;

     }

     static bool help_fun(Interval i1,Interval i2)

     {

         return i1.start<i2.start;

     }

 };

 int main()

 {

     vector<Interval> intervals={Interval(,),\

                                 Interval(,),\

                                 Interval(,),\

                                 Interval(,)};

     Solution sol;

     vector<Interval> ret = sol.merge(intervals);

     for(int i=;i<ret.size();i++){

         cout<<ret[i].start<<" "<<ret[i].end<<endl;

     }

     return ;

 }

巴特西

[LeetCode] Merge Intervals 排序sort

最新文章

热门文章