Leetcode 57. Insert Interval

https://leetcode.com/problems/insert-interval/

Insert, sort and merge. It is very similar with last problem.

Solution:

# T:O(N) S:O(n)
class Solution:
    # @param {Interval[]} intervals
    # @param {Interval} newInterval
    # @return {Interval[]}
    def insert(self, intervals, newInterval):
        intervals.append(newInterval)
        def merge(intervals):
            intervals.sort(key = lambda x: x.start)
            N, ret = len(intervals), []
            for i in xrange(N):
                if not ret:
                    ret.append(intervals[i])
                else:
                    L = len(ret)
                    if ret[L-1].start<=intervals[i].start<=ret[L-1].end:
                        ret[L-1].end = max(intervals[i].end, ret[L-1].end)
                    else:
                        ret.append(intervals[i])
            return ret
        a = merge(intervals)
        return a

Run Time: 108 ms