Python O(nlgn) iteration Solution


  • 0
    class Solution(object):
        def merge(self, intervals):
            ans = []
            intervals.sort(key = lambda x: x.start)
            for interval in intervals:
                if not ans:
                    ans.append([interval.start, interval.end])
                elif interval.start <= ans[-1][1]:
                    ans[-1][1] = max(ans[-1][1], interval.end)
                else:
                    ans.append([interval.start, interval.end])
            return ans
    

  • 0
    H

    It is clearly not O(n) solution.

    intervals.sort(key = lambda x: x.start)
    

    runs at least in O(n logn).


  • 0

    @hongjian3 You are right, thanks for pointing out :)


Log in to reply
 

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