24ms c++ using set


  • 0
    P

    I guess the running time distribution is wrong.

    typedef pair<int,int> ii;
    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            vector<Interval> mer;
            if(intervals.size()==0) return mer;
            set<ii> interset;
            for(Interval in:intervals) interset.insert(ii(in.start,in.end));
            __typeof(interset.begin()) it=interset.begin();
            int st = it->first,ed = it->second;
            it++;
            while(it!=interset.end()){
                if(it->first>ed){
                    mer.push_back(Interval(st,ed));
                    st = it->first;
                    ed = it->second;
                }
                else ed = max(ed,it->second);
                it++;
            }
            mer.push_back(Interval(st,ed));
            return mer;
        }
    };

  • 0
    P

    20 ms Improved using a defined operator

    class le{
    public:
        bool operator ()(const Interval &i1,const Interval &i2){
            if(i1.start!=i2.start) return i1.start<i2.start;
            return i1.end<i2.end;
        }
    };
    
    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            vector<Interval> mer;
            if(intervals.size()==0) return mer;
            sort(intervals.begin(),intervals.end(),le());
            int st = intervals[0].start,ed = intervals[0].end;
            for(Interval in:intervals){
                if(in.start>ed) {
                    mer.push_back(Interval(st,ed));
                    st = in.start;
                    ed = in.end;
                }
                else ed = max(ed,in.end);
            }
            mer.push_back(Interval(st,ed));
            return mer;
        }
    };

Log in to reply
 

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