LeetCode 刷题记录: 56. Merge Intervals [Python]

原题

https://leetcode.com/problems/merge-intervals/

Given a collection of intervals, merge all overlapping intervals.

思路

先对数组排序,然后遍历数组。设定两个变量记录左边界和右边界。

  1. 对于每个范围,当其左值小于记录的右边界时,即这个范围可以被merge。此时右边界为右值与右边界的最大值,在结果数组更新最后一项的右值。

  2. 否则重新设定左边界与右边界,并将新的范围记录至结果中。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    if len(intervals)==0: return []
    left=right=-1
    intervals.sort()
    res=[]
    for intv in intervals:
    if right>=intv[0]:
    right=max(intv[1],right)
    res[-1][1]=right

    else:
    left,right=intv
    res.append(intv)
    return res

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×