56. 合并区间(python)

题目描述（中等）

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路

1. 记intervals为所有区间的集合；ans为输出的区间集合，初始时ans的第一个区间是第一个intervals的区间。
2. 将intervals的所有区间按起始元素大小升序排序
3. 依次遍历每个区间，如果intervals第 i 个区间的始端大于ans最后一个区间的末端，则将第 i 个区间添加进ans；否则，判断当intervals第 i 个区间的末端大于ans最后一个区间的始端时，将ans最后一个区间的末端替换成第 i 个intervals区间的末端

# 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]
        """
        if len(intervals)1:
            return intervals
        ans=[]
        intervals = sorted(intervals,key = lambda start: start.start)
        ans.append(intervals[0])
        for i in range(1,len(intervals)):
            if ans[-1].endintervals[i].start:
                ans.append(intervals[i])
            elif intervals[i].endans[-1].end:
                ans[-1].end=intervals[i].end                             
        return ans

以上代码是在LeetCode上的，LeetCode上面内部对intervals定义为intervals[i].start=intervals[i][0] ,intervals[i].end=intervals[i][1] ，而如果直接在pycharm上面运行python3文件的话，不需要这么麻烦，以下为代码：

    def merge(intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        if len(intervals)1:
            return intervals
        ans=[]
        intervals.sort() 
        ans.append(intervals[0])
        for i in range(1,len(intervals)):
            if ans[-1][1]intervals[i][0]:
                ans.append(intervals[i])
            elif intervals[i][1]ans[-1][1]:
                ans[-1][1]=intervals[i][1]
        return ans