Simple O( nlog(n) ) solution using Map


  • 0
    J
    vector<Interval> merge(vector<Interval>& intervals) {
        map< int, int > a;
        vector<Interval> res;
        if( intervals.size() <= 1) return intervals;
        
        // add to ordered map O( nlog(n) )
        for( auto i: intervals ) a[i.start] = a[i.start] > i.end? a[i.start] : i.end;
    
        // merge sorted intervals O( n )
        int s = a.begin()->first, e=a.begin()->second;
        for( auto i: a ){
            
            if( e >= i.first ) e = e > i.second? e : i.second;
            else {
                res.push_back(Interval(s,e));
                s = i.first;
                e = i.second;
            }
        }
        //add last interval
        res.push_back(Interval(s,e));
        return res;
    }

Log in to reply
 

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