Simple O(nlogn) solution exceeding time?


  • 0
    E
    class Solution {
    public:
    static bool compare(Interval& i1, Interval& i2) {
        return i1.start<i2.start;
    }
    static bool overlap(Interval& i1, Interval& i2) {
    
        return i1.end>i2.start;
    }    
    
    vector<Interval> merge(vector<Interval>& intervals) {
        if(intervals.size() < 2)
            return intervals;
    
        sort(intervals.begin(), intervals.end(), compare);
        
        for(int i = 1; i < intervals.size()-1; ) {
            if(overlap(intervals[i-1], intervals[i])) {
                if(intervals[i-1].end < intervals[i].end) {
                    intervals[i-1].end = intervals[i].end;
                }
                intervals.erase(intervals.begin()+i);
            }
            else {
                i++;
            }
        }
        return intervals;
    }   
    
    };

  • 0

    That's not O(n log n) but O(n^2).


  • 0
    E

    how is it O(n^2)? I thought sort was O(n log n) and then I loop through the list which is O(n).

    is it cause of the erase?


  • 0

    Yes, erase. Takes linear time.


Log in to reply
 

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