56. Merge Intervals Medium 2509194FavoriteShare

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.
思路：
对所有按键值排序，看下一个是和它合并还是单独存储

class Solution(object):
    def merge(self, intervals):
        ans = []
        # 使用下标表示interval里的是按哪个排序
        for interval in sorted(intervals, key=lambda x: x[0]):
            # 如果初始或者当前与上一个足够拉开差距，直接压入
            if not ans or interval[0] > ans[-1][1]:
                ans.append(interval)
            # 否则扩展上一个ans的范围
            else:
                ans[-1][1] = max(ans[-1][1], interval[1])
        return ans

solu=Solution()
intervals=[[1,3],[2,6],[8,10],[15,18]]
print(solu.merge(intervals))