难度：中等

题目内容：

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

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

题解:

首先头疼的问题就是如果区间随意排放就很难搞
所以先按左端点排个序
然后从左向右挨个合并就好啦

image.png

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 0:
            return []
        intervals.sort(key = lambda x: x[0])# 排序
        lastsec = intervals[0][:]
        i = 1
        
        while i<= len(intervals) - 1:
            #print(lastsec,intervals)
            if lastsec[0] <= intervals[i][0] and lastsec[1] >= intervals[i][0]:
                lastsec = self.me(lastsec,intervals[i])
                intervals[i-1] = lastsec[:]
                intervals.pop(i)
            else:
                lastsec = intervals[i]
                i += 1
        return intervals

    def me(self,l1,l2):
        if l1[0]<= l2[0] and l1[1] >= l2[1]:
            return l1
        elif l1[0]<= l2[0] and l1[1] < l2[1]:
            return [l1[0],l2[1]]
        elif l2[0]<= l1[0] and l2[1] < l1[1]:
            return l2
        elif l2[0]<= l1[0] and l2[1] < l1[1]:
            return [l2[0],l1[1]]