O(nlogn) time O(n) space Python, converting to linked-list


  • 2
    class IntervalNode(object):
        def __init__(self, interval):
            self.interval = interval
            self.next = None
            
    class Solution(object):
        def merge(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: List[Interval]
            """
            intervals = sorted(intervals, key=lambda x:x.start)
            pre = None
            head = None
            ans = []
            for i in xrange(0, len(intervals)):
                interval = intervals[i]
                node = IntervalNode(interval)
                if not head:
                    head = node
                if pre:
                    pre.next = node
                pre = node
            
            p = head
            while p:
                if p.next and p.next.interval.start <= p.interval.end:
                    p.interval.end = max(p.next.interval.end, p.interval.end)
                    p.next = p.next.next
                else:
                    p = p.next
            
            p = head
            while p:
                ans.append(p.interval)
                p = p.next
            return ans
    

  • 0
    A

    I'm curious why you chose to approach the problem this way. Was it just to practice building and using linked-lists?


  • 1

    @acmiyaguchi Yes, just for fun!


  • 0
    A

    Awesome! Just a few nits. I think it looks more pythonic to use an iterator like the following

    for interval in intervals:
        ...
    

    as opposed to using an index, especially if you aren't going to use the index for other things.

    for i in xrange(0, len(intervals)):
       interval = intervals[i]
    

    Also, most list-like objects have an internal sort method that does sorting in place instead of creating a new object. You could replace sorted(...) with intervals.sort(key=lambda x: x.start).

    Nice implementation of a linked list :)


Log in to reply
 

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