What's wrong with my simple answer? It's TLE but it's O(n*logn).


  • 0
    D
    var merge = function(intervals) {
    intervals.sort(function(a,b){return a.start-b.start});
    present=0;
    next=1;
    len=intervals.length;
    while(next<len)
    {
        console.log(intervals[present],intervals[next]);
        if(intervals[next].end<=intervals[present].end)
        {
            intervals.splice(next,1);
            len--;
            console.log("devour",intervals);
        }
        else if(intervals[next].end>intervals[present].end&&intervals[next].start<=intervals[present].end)
        {
            intervals[present].end=intervals[next].end;
            intervals.splice(next,1);
            len--;
            console.log("merge",intervals);
        }
        else 
        {
            present++;
            next++;
            console.log("nothing happens",intervals);
        }
        
    }
    
    return intervals;
    

    };


  • 0
    Z

    I don't know about javascript but I guess

    intervals.splice(next,1);
    

    is O(n).

    I got same problem with my C++ vector.erase(vector.begin() + i)

    Looks like we can't do this in-place?


  • 0

    It gets accepted if you just remove the logging.


Log in to reply
 

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