Leetcode 56. Merge Intervals

https://leetcode.com/problems/merge-intervals/

Merge one by one. Sorting is needed and note the not overlapping situation.

Solution:

# T:O(nlgn) S:O(n)
# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    # @param {Interval[]} intervals
    # @return {Interval[]}
    def merge(self, intervals):
        N, ret = len(intervals), []
        intervals.sort(key = lambda x: x.start)
        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(ret[L-1].end, intervals[i].end)
                else:
                    ret.append(intervals[i])
        return ret

Run Time: 96 ms