乘风原创程序

  • LeetCode——56. 合并区间
  • 2021/2/23 10:11:23
  • 56. 合并区间

    题目

    以数组 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] 可被视为重叠区间。
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/merge-intervals
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    

    题解思路

    1>源代码

    class Solution:
        def merge(self, intervals: List[List[int]]) -> List[List[int]]:
            intervals.sort()
            out = []
            length = len(intervals)
            i = 1
            out.append(intervals[0])
            while i<length:
                if len(out)==0 or out[-1][1]<intervals[i][0]:
                    out.append(intervals[i])
                else:
                    out[-1][1] = max(out[-1][1], intervals[i][1])
                i+=1
            return out
    
    

    2>算法介绍

    本题初看起来没什么思路,但细想了一下发现,如果我们对输入列表按照每个子列表的第一个元素进行排序,如果出现合并情况,则可合并的两个子列表一定是相邻的。

    想明白了这一点我们就可以在一次遍历中完成out列表的建立,具体步骤详见代码。

    本文地址:https://blog.csdn.net/HizT_1999/article/details/113965371