leetcode刷题-56合并区间

题目

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

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]

思路

通过设置一个移动的判定区间，来完成区间的合并

首先对数组排序，使其以左区间为标准，从小到大，依次排序，然后依次读出数组：

当取出的数组的left <= 判定区间right 且取出的数组的right >= 判定区间right :则认为两个区间有重合，合并区间

当取出的数组的left > 判定区间right:不存在重合，当新区间作为判定区间。

实现

class Solution:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals.sort()

        result = list()

        if not intervals:

            return []

        result.append(intervals[0])

        for idx in intervals:

            left = result[-1][0]

            right = result[-1][1]

            if idx[0] <= right and idx[1] >= right:

                result[-1][1] = idx[1]

            elif idx[0] > right:

                result.append(idx)

        return result

巴特西

leetcode刷题-56合并区间

题目

思路

实现

最新文章

热门文章