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
O(nlogn) time O(n) space Python, converting to linkedlist



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 listlike objects have an internal sort method that does sorting in place instead of creating a new object. You could replace
sorted(...)
withintervals.sort(key=lambda x: x.start)
.Nice implementation of a linked list :)