当前位置: 首页 > news >正文

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

思路:
首先我们根据区间的起点做了一个排序,起点小的靠前,起点大的靠后;
其次我们根据前一个区间的终点和后一个区间的起点是否有重合,判断区间是否可以合并;
最后,合并后的区间起点一定是靠前的那个区间的起点,终点是两个区间中终点更大的那个;
从两个区间的合并过程中我们可以看出,合并区间:

根据区间起点排序;
维护一个当前合并的区间[start, end]
判断当前区间是否可以合并到当前的合并区间;可以则更新合并区间的终点,不可以这个区间作为新的一个合并区间去合并后面的区间。

python:
如果我们每次判断当前区间是否可以合并到当前的合并区间,那么最后一个区间无论是加入到原有的合并区间还是自己作为一个新的区间,最后一个合并区间都没有加入到结果列表中。因此,最后遍历完所有区间,要把当前的合并区间加入结果列表中。

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:# 对区间进行升序排序intervals.sort()# 初始化合并区间为首个区间start,end=intervals[0]# 结果列表res=[]for (s,e) in intervals:# 判断每一个区间能否加入当前合并区间if s>end:# 当前区间不能加入当前的合并区间,记录当前合并区间,以此区间作为新的合并区间res.append([start,end])start,end=s,eelse:# 当前区间加入当前的合并区间,更新合并区间的终点end=max(end,e)# 补充加入最后一个合并区间res.append([start,end])return res
http://www.lryc.cn/news/313558.html

相关文章:

  • C++:List的使用和模拟实现
  • 20个Python函数程序实例
  • Wireshark——获取捕获流量的前N个数据包
  • 006-浏览器输入域名到返回
  • 【kubernetes】关于k8s集群如何将pod调度到指定node节点?
  • 【框架】React和Vue的异同
  • 如何选择阅读软件技术学习书籍
  • 做抖店用平板能代替电脑操作吗?抖店运营相关注意事项,注意规避
  • 【FastChat】用于训练、服务和评估大型语言模型的开放平台
  • 从根到叶:深入理解二叉搜索树
  • 网络信息安全:11个常见漏洞类型汇总
  • 阿里云服务器使用教程_2024建站教程_10分钟网站搭建流程
  • 【排序算法】推排序算法解析:从原理到实现
  • Python爬虫实战(基础篇)—13获取《人民网》【最新】【国内】【国际】写入Word(附完整代码)
  • 常见控件应用
  • 什么是降压恒流芯片?它有什么作用?
  • 14:00面试,15:00就出来了,问的问题过于变态了。。。
  • Maven的settings.xml配置
  • 利用redis实现秒杀功能
  • vscode 使用ssh进行远程开发 (remote-ssh),首次连接及后续使用,详细介绍
  • rabbitmq总结
  • 专利预审是什么
  • 淘宝商品详情数据丨商品搬家丨商品采集丨商城建站
  • redis(1)-key-value-基本概念
  • cocos creator 3.7.2使用shader实现图片扫光特效
  • 【C++杂货铺】详解string
  • 算法刷题day20:二分
  • 【Spring云原生】Spring Batch:海量数据高并发任务处理!数据处理纵享新丝滑!事务管理机制+并行处理+实例应用讲解
  • docker ubuntu20.04 安装教程
  • 防御保护----IPSEC VPPN实验