leetcodeday56 –合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

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

示例 2：

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

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

第一次尝试：

# [56] 合并区间
#

# @lc code=start
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # def takeSecond(elem):
        #     return elem[0]
       
        # intervals.sort(key=takeSecond)       
        def submatch(intervals):
            rev=list()
            i=0
            j=0
            lens=len(intervals)
            intervals.sort(key=lambda x: (x[0], x[1]))
            maxy=0 
            while i<lens:
                maxy=max(maxy,intervals[i][1])          
                if j<lens-1 and intervals[i][1]>=intervals[j+1][0]:
                    maxy=max(maxy,intervals[j+1][1])   
                    j=j+1         
                else:
                    maxy=max(maxy,intervals[j][1]) 
                    rev.append([intervals[i][0],maxy])
                    i=j+1
                    j=i
            return rev
        
        rev=submatch(intervals)
        while rev!=submatch(rev):
            rev=submatch(rev)
        return rev