美文网首页算法学习
算法题--合并区间

算法题--合并区间

作者: 岁月如歌2020 | 来源:发表于2020-04-14 15:39 被阅读0次
    image.png

    0. 链接

    题目链接

    1. 题目

    Given a collection of intervals, merge all overlapping intervals.

    Example 1:

    Input: [[1,3],[2,6],[8,10],[15,18]]
    Output: [[1,6],[8,10],[15,18]]
    Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
    

    Example 2:

    Input: [[1,4],[4,5]]
    Output: [[1,5]]
    Explanation: Intervals [1,4] and [4,5] are considered overlapping.
    

    NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

    2. 思路1:先按照左端点排序+再逐个合并区间

    1. 按照各个区间左端值升序排列,再从左到右合并两个相邻区间,遇到不能合并的,则收集到结果里;否则修改区间右端点值

    3. 代码

    # coding:utf8
    from typing import List
    
    
    class Solution:
        def merge(self, intervals: List[List[int]]) -> List[List[int]]:
            if len(intervals) <= 1:
                return intervals
    
            intervals.sort(key=lambda x: x[0], reverse=False)
    
            last_idx = 0
    
            for i in range(1, len(intervals)):
                last_interval = intervals[last_idx]
                interval = intervals[i]
                if interval[0] <= last_interval[1] <= interval[1]:
                    last_interval[1] = interval[1]
                elif last_interval[1] < interval[0]:
                    last_idx += 1
                    last_interval = intervals[last_idx]
                    last_interval[0] = interval[0]
                    last_interval[1] = interval[1]
    
            return intervals[:last_idx + 1]
    
    
    solution = Solution()
    print(solution.merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
    print(solution.merge([[1,4],[4,5]]))
    print(solution.merge([]))
    print(solution.merge([[1, 4], [0, 1]]))
    
    

    输出结果

    [[1, 6], [8, 10], [15, 18]]
    [[1, 5]]
    []
    [[0, 4]]
    

    4. 结果

    image.png

    相关文章

      网友评论

        本文标题:算法题--合并区间

        本文链接:https://www.haomeiwen.com/subject/xhrtvhtx.html