标签搜索

56. 合并区间

Lan
Lan
2022-08-16 / 0 评论 / 34 阅读 / 正在检测是否收录...

以数组 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

第一次提交(写的比较乱,然后也没通过):

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        a = set()
        for interval in intervals:
            for num in range(interval[0], interval[1] + 1):
                a.add(num)
        result = [[a.pop()]]
        for c in a:
            if (result[-1][-1] + 1) == c:
                result[-1].append(c)
            else:
                result[-1] = [result[-1][0], result[-1][-1]]
                result.append([c])
        result[-1] = [result[-1][0], result[-1][-1]]
        return result

www.lanol.cn
官方答案:

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        result = []
        for interval in intervals:
            if not result or result[-1][1] < interval[0]:
                result.append(interval)
            else:
                result[-1][1] = max(result[-1][1], interval[1])
        return result

www.lanol.cn
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

0

评论 (0)

取消