Fast and simple C++ solution, 16ms, beats 100%, O(n) time


  • -2
    J

    here is a fast and simple C++ solution, 16ms, beats 100%, O(n)

    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;
        }
    };

  • 0
    Y

    Why was this solution down voted?


  • 1
    X

    if you sort(), the time complexity is not o(n)


  • 0
    A

    @joe.zhang.nh Since you use sort, you can get at best O(nlogn).


Log in to reply
 

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