16ms C++ solution, beat 100%.


  • 0
    A
    class Solution {
    private:
        static bool compare(Interval& i1, Interval& i2) {
            return i1.start<i2.start;
        }
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            if (intervals.size()<2) return intervals;
    
            vector<Interval> M_I;
            sort(intervals.begin(),intervals.end(),compare);
    
            auto it=intervals.cbegin();
            Interval in=*it;
            ++it;
            for (it;it!=intervals.cend();++it) {
                if (it->start>in.end) {M_I.push_back(in); in=*it;}
                else in.end=max(in.end,it->end);
            }
            M_I.push_back(in);
            return M_I;
        }
    };

  • 0
    J

    // simple solution, 16ms, beats 100%

    bool operator<(const Interval& l, const Interval& r){
    return l.start < r.start;
    }

    class Solution {
    public:
    vector<Interval> merge(vector<Interval>& intervals) {
    vector<Interval> result;
    if(intervals.empty()){
    return result;
    }
    int size = intervals.size();
    result.reserve(size);
    sort(intervals.begin(), intervals.end());
    Interval cur(intervals[0]);
    for(int i = 1; i<size; ++i){
    if( cur.end<intervals[i].start){
    result.push_back(cur);
    cur = intervals[i];
    }else {
    cur.end = max(cur.end, intervals[i].end);
    }
    }
    result.push_back(cur);
    return result;
    }
    };


Log in to reply
 

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