8 - Medium - 合并区间

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

示例 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] 可被视为重叠区间。

AC但是很慢

# 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]
        """
        i = 0
        while True:
            if i >= len(intervals):
                break
            one_interval = intervals[i]
            for rest_interval in intervals[:i] + intervals[i+1:]:
                new_interval = None
                if one_interval.start <= rest_interval.end <= one_interval.end and rest_interval.start <= one_interval.start:
                    new_interval = Interval(rest_interval.start, one_interval.end)
                elif one_interval.start <= rest_interval.start <= one_interval.end and rest_interval.end >= one_interval.end:
                    new_interval = Interval(one_interval.start, rest_interval.end)
                elif one_interval.start <= rest_interval.start and one_interval.end >= rest_interval.end:
                    new_interval = Interval(one_interval.start, one_interval.end)
                elif one_interval.start >= rest_interval.start and one_interval.end <= rest_interval.end:
                    new_interval = Interval(rest_interval.start, rest_interval.end)
                if new_interval:
                    intervals.pop(i)
                    i -= 1
                    intervals.remove(rest_interval)
                    intervals.append(new_interval)
                    break
            i += 1
        return intervals

64ms，先排序，之后再合并时，仅看merged[-1].end 和当前interval有没有重合，没有则直接append，有则比较哪个end更大，保存更大的end

class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x.start)

        merged = []
        for interval in intervals:
            # if the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged or merged[-1].end < interval.start:
                merged.append(interval)
            else:
            # otherwise, there is overlap, so we merge the current and previous
            # intervals.
                merged[-1].end = max(merged[-1].end, interval.end)
        
        return merged