Day 36 贪心算法 part05 : 435. 无重叠区间 763.划分字母区间 56. 合并区间

这篇具有很好参考价值的文章主要介绍了Day 36 贪心算法 part05 : 435. 无重叠区间 763.划分字母区间 56. 合并区间。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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] 可被视为重叠区间。

提示:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

通过次数

701.1K

提交次数

1.4M

通过率

49.6%

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        time: O(nlogn) 主要由排序操作决定,其中 n 是区间的个数。
        space: O(n) 用于存储结果区间。
        """

        result = []

        # base case: 区间集合为空直接返回
        if not intervals:
            return result  

        # 按区间的起始点进行排序
        intervals.sort(key=lambda x: x[0])

        result.append(intervals[0])  # 第一个区间可以直接放入结果集中 

        for i in range(1, len(intervals)):
            current_start, current_end = intervals[i]
            last_start, last_end = result[-1]

            # 如果当前区间与结果列表中的最后一个区间不重叠,则将当前区间添加到结果列表中
            if current_start > last_end:
                result.append([current_start, current_end]) # intervals[i]也可以
            else:
                # 否则,合并这两个区间
                # 合并只需更新结果集最后一个区间的右边界,因为根据排序,左边界已经是最小的
                result[-1][1] = max(current_end, last_end)
                
        return result 

 文章来源地址https://www.toymoban.com/news/detail-707097.html

到了这里,关于Day 36 贪心算法 part05 : 435. 无重叠区间 763.划分字母区间 56. 合并区间的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 贪心算法part5 | ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

    重叠问题都需要先排好序,再贪心 搞清楚左右区间,重叠的条件。 要找出最少删除的数量,也就是找出重叠空间的数量,然后用长度减去即可。 这里提供一种与452.用最少数量的箭引爆气球 (opens new window)、435.无重叠区间 (opens new window)相同的思路。 统计字符串中所有字符的

    2024年02月09日
    浏览(59)
  • LeetCode 36天 | 435.无重叠区域 763.划分字母区间 56.合并区间

    435. 无重叠区间 左边排序,右边裁剪为当前最小的 763. 划分字母区间 自己写出来的题,虽然之前做过一遍了。 自己的写法虽然比较难看,但是也列出来了。 再给一个卡尔的写法 56. 合并区间 重叠区域的题目大都要按左边界先排序。学了个lambda表达式。可以直接将一个区域放

    2024年02月20日
    浏览(72)
  • DAY35 435. 无重叠区间 + 763.划分字母区间 + 56. 合并区间

    题目要求:给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。 示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后,剩下的区间没

    2024年02月08日
    浏览(47)
  • 【Leetcode60天带刷】day35——452. 用最少数量的箭引爆气球,435. 无重叠区间,763.划分字母区间

    ​ 452. 用最少数量的箭引爆气球 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组  points  ,其中 points[i] = [xstart, xend]  表示水平直径在  xstart  和  xend 之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点  完全垂直  

    2024年02月11日
    浏览(63)
  • Day36 贪心算法 part05

    一个字母区间仅有几个字母 前一个字母区间有的字母后面都没有 天才举一反三写出来了

    2024年02月19日
    浏览(53)
  • LeetCode_贪心算法_中等_763.划分字母区间

    给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s。返回一个表示每个字符串片段的长度的列表。 示例 1: 输入:s = “ababcbacadefegdehijhklij” 输出

    2024年02月14日
    浏览(75)
  • day31贪心算法 用最少数量的箭引爆气球 和无重叠区间

    题目描述 题目分析: x轴向上射箭,12一支,重叠的需要一支,3-8一支,7-16一支 返回2; 就是让重叠的气球尽量在一起,局部最优;用一支弓箭,全局最优就是最少弓箭; 如何去寻找重叠的气球?和记录弓箭数? 1.对所有气球排序;(左边界排序如上图); 2. if 如果第i个气

    2024年02月16日
    浏览(46)
  • LeetCode-763. 划分字母区间【贪心 哈希表 双指针 字符串】

    给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。 注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。 示例 1: 输入:s = “ababcbacadefegdehijhklij” 输

    2024年04月10日
    浏览(54)
  • Day31- 贪心算法part05

    题目一:453. 无重叠区间  435. 无重叠区间 给定一个区间的集合  intervals  ,其中  intervals[i] = [starti, endi]  。返回  需要移除区间的最小数量,使剩余区间互不重叠  。 主要思想是优先保留结束时间早的区间,这样留给其他区间的空间就更多,从而减少需要移除的区间数量

    2024年01月19日
    浏览(43)
  • 力扣 435. 无重叠区间

    题目来源:https://leetcode.cn/problems/non-overlapping-intervals/description/ C++题解1:对区间进行排序,根据区间的末端进行排序,小的在前,大的在后;由于有重复区间,我们拿后面的区间去看是否跟前面的区间重合,如果后面区间的前端大于前面区间的后端,则说明重合;但在排序会

    2024年02月15日
    浏览(92)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包