C++ 19 ms Sort first than merge.


  • 0
    D

    First topic. ^^ Hope can help someone.

    class Solution {
    public:
      /*template<typename P> struct Cmpnew{
        bool operator()(const P &p1, const P &p2){
          if(p1.start < p2.start) return true;
          if(p1.start == p2.start) return p1.end < p2.end;
          return false;
        }
      };*/
      //template for Cmpnew not work well, so I rewrite but leave the original one  
      struct Cmpnew{
        bool operator()( Interval &p1,  Interval &p2){
          if(p1.start < p2.start) return true;
          if(p1.start == p2.start&&p1.end < p2.end) return true;
          return false;
        }
      };
      vector<Interval> merge(vector<Interval>& intervals) {
        int n=intervals.size();
        if(n==0) return intervals;
        vector<Interval> res;
        sort(intervals.begin(),intervals.end(),Cmpnew());
        //sort(intervals.begin(),intervals.end(),Cmpnew<Interval>());
        int curs,cure,start,end=0x80000000;
        for(int i=0;i<intervals.size();i++){
          curs=intervals[i].start;
          cure=intervals[i].end;
          if(end<curs){
            if(i!=0){
              res.push_back(Interval(start,end));
    	}
    	start=curs;
    	end=cure;
          }
          else{
            start=min(curs,start);
            end=max(cure,end);
          }
        }
        res.push_back(Interval(start,end));
        return res;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.