[SwapLine]56. Merge Intervals

• 分类：SwapLine
• 时间复杂度: O(n)

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

代码：

方法:

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

class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        res=[]
        if intervals==None or len(intervals)==0:
            return res
        elif len(intervals)==1:
            return intervals
        
        intervals.sort(key=lambda x:x.start)
        last=intervals[0]
        for i in range(len(intervals)):
            if intervals[i].start<=last.end:
                last.end=max(last.end,intervals[i].end)
            else:
                res.append(last)
                last=intervals[i]
        res.append(last)
        return res

讨论：

1.一道轻松的middle题，思路和skyline是一样的，感觉这种要合并区间的首先都是要排个序
2.然后这里是如果current.start在之间的区间范围内，那么last.end要更新,不然的话就结束，把last放到res里，然后再搞个新的last。
3.最后这个res.append千万别忘了加！很重要！