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

【算法】插入区间

难度:中等

题目:

给你一个 无重叠的 ,按照区间起始端点排序的区间列表 intervals,其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束,并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval,使得 intervals 依然按照 starti 升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]

示例 2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

提示:

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= 105

解题思路:

这道题目的解题思路主要是遍历给定的区间列表,并根据新插入的区间newInterval与当前遍历到的区间的关系,决定如何合并或插入新区间。具体步骤如下:

  1. 初始化:创建一个新的结果数组result,用于存放合并后的区间。
  2. 处理新区间前的区间:遍历区间列表,直到遇到第一个结束点大于等于newInterval的开始点的区间。在此之前的所有区间可以直接加入结果数组,因为它们与newInterval不重叠。
  3. 合并重叠区间:当遇到与newInterval重叠的区间时,更新newInterval的起始和结束点,以覆盖所有重叠的区间。继续遍历,直到不重叠为止。
  4. 将合并后的区间加入结果:将经过更新后的newInterval加入结果数组。
  5. 处理新区间后的区间:将剩余的区间(即结束点小于newInterval结束点的所有区间已处理完毕)直接加入结果数组。
  6. 返回结果:返回合并后的区间列表result。

JavaScript 实现:

function insert(intervals, newInterval) {const result = [];let i = 0; // 用于遍历intervals的指针// 步骤2:处理新区间前的区间while (i < intervals.length && intervals[i][1] < newInterval[0]) {result.push(intervals[i]);i++;}// 步骤3:合并重叠区间while (i < intervals.length && intervals[i][0] <= newInterval[1]) {newInterval[0] = Math.min(newInterval[0], intervals[i][0]);newInterval[1] = Math.max(newInterval[1], intervals[i][1]);i++;}result.push(newInterval);// 步骤4:将合并后的区间加入结果// 步骤5:处理新区间后的区间while(i < intervals.length){result.push(intervals[i]);i++;}return result;
}
// 示例
// const intervals = [[1,3],[6,9]];
// const newInterval = [2,5];
// console.log(insert(intervals, newInterval)); // 输出: [[1,5],[6,9]]

这段代码首先定义了insert函数,它接收一个区间列表intervals和一个新插入的区间newInterval作为参数,然后按照上述步骤处理并返回合并后的区间列表。

相关文章:

【算法】插入区间

难度&#xff1a;中等 题目&#xff1a; 给你一个 无重叠的 &#xff0c;按照区间起始端点排序的区间列表 intervals&#xff0c;其中 intervals[i] [starti, endi] 表示第 i 个区间的开始和结束&#xff0c;并且 intervals 按照 starti 升序排列。同样给定一个区间 newInte…...

C++ 代码实现socket 类使用TCP/IP进行通信 (windows 系统)

C 代码实现socket 类使用TCP/IP进行通信 &#xff08;windows 系统&#xff09; TCP客户端通信常规步骤&#xff1a; 1.初始换socket环境 2.socket()创建TCP套接字。 3.connect()建立到达服务器的连接。 4.与客户端进行通信&#xff0c;recv()/send()接受/发送信息&#xff0…...

前后端分离项目部署,vue--nagix发布部署,.net--API发布部署。

目录 Nginx免安装部署文件包准备一、vue前端部署1、修改http.js2、npm run build 编译项目3、解压Nginx免安装,修改nginx.conf二、.net后端发布部署1、编辑appsetting.json,配置跨域请求2、配置WebApi,点击发布3、配置文件发布到那个文件夹4、配置发布相关选项5、点击保存,…...

【BUG】已解决:UnicodeDecodeError: ‘utf-8’ codec can’t decode bytes in position 10

UnicodeDecodeError: ‘utf-8’ codec can’t decode bytes in position 10 目录 UnicodeDecodeError: ‘utf-8’ codec can’t decode bytes in position 10 【常见模块错误】 【解决方案】 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#x…...

C++ | QQ后端暑期实习面试

tcp三次握手&#xff0c;四次挥手 断点续传 文件断点续传是一种机制&#xff0c;允许在网络传输中的文件传输过程中出现断开连接或传输中断的情况下&#xff0c;能够恢复传输并继续传输未完成的部分。其原理如下&#xff1a; 检测支持&#xff1a;首先&#xff0c;服务器端和…...

实用网站推荐

​ 学习 前端 精简CSS格式 Font Awesome 图标库 BootCDN 加速服务 合集 AI工具集 动漫、音乐 娱乐 嗷呜动漫 奈飞同步 视频下载 B站视频解析下载 文件操作 ioDraw制作图 Convertio — 文件转换器 PDF处理 ​LOGO...

Linux |Nethogs 监控网络使用情况

引言 互联网上为 Linux 系统提供了许多开源的网络监控工具。例如&#xff0c;你可以利用 iftop 命令来监测网络带宽的消耗&#xff0c;使用 netstat 或 ss 命令来获取网络接口的统计信息&#xff0c;或者通过 top 命令来查看系统中正在运行的进程。 然而&#xff0c;如果你真正…...

大语言模型训练过程中,怎么实现算力共享,采用什么分片规则和共享策略

目录 大语言模型训练过程中,怎么实现算力共享,采用什么分片规则和共享策略 一、算力共享的实现 二、分片规则与共享策略 三、总结 DeepSpeed、Megatron-LM是什么 DeepSpeed ZeRO技术一般不实现调参的 ZeRO技术的实现方式 ZeRO与调参的关系 NCCL是什么 一、NCCL概…...

JCR一区级 | Matlab实现TTAO-Transformer-LSTM多变量回归预测

JCR一区级 | Matlab实现TTAO-Transformer-LSTM多变量回归预测 目录 JCR一区级 | Matlab实现TTAO-Transformer-LSTM多变量回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.【JCR一区级】Matlab实现TTAO-Transformer-LSTM多变量回归预测&#xff0c;三角拓扑聚合…...

斐波那契数列(Fibonacci)数列 c++详解

Fibonacci数列是一个在数学和计算机科学中非常著名的数列。这个数列以其特殊的递推关系而闻名&#xff0c;也因其在自然界中的多次出现而引人注目。 定义&#xff1a; Fibonacci数列的定义如下&#xff1a; F(0) 0F(1) 1对于 n > 1&#xff0c;F(n) F(n-1) F(n-2) 也就…...

第三届人工智能、物联网和云计算技术国际会议(AIoTC 2024,9月13-15)

第三届人工智能、物联网与云计算技术国际会议(AIoTC 2024)将于2024年9月13日-15日在中国武汉举行。 本次会议由华中师范大学伍伦贡联合研究院与南京大学联合主办、江苏省大数据区块链与智能信息专委会承办、江苏省概率统计学会、江苏省应用统计学会、Sir Forum、南京理工大学、…...

家具购物小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;家具分类管理&#xff0c;家具新品管理&#xff0c;订单管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;家具新品&#xff0c;家具公告&#xff0…...

测试面试宝典(三十四)—— token是做什么用的?

Token 在软件系统中通常具有多种重要用途。 首先&#xff0c;它用于身份验证和授权。用户登录成功后&#xff0c;系统会生成一个唯一的 token 并返回给客户端&#xff0c;客户端后续的请求携带这个 token 来证明其身份和访问权限&#xff0c;避免了每次请求都需要重新输入用户…...

计算机网络基础:4.HTTP与HTTPS

一、回顾设定 想象你在经营一家繁忙的餐厅&#xff0c;顾客们通过点餐系统&#xff08;网卡&#xff09;下单&#xff0c;订单被前台&#xff08;路由器&#xff09;接收并分发到各个厨房区域&#xff08;网络设备&#xff09;。光猫像是食材供应商&#xff0c;通过高效的物流系…...

【深度学习入门】安装conda/miniconda、所需包类、CUDA与conda/Miniconda间的关系

深度学习入门 须知 本教程跟随李沐老师课程随笔&#xff0c;课程链接点击此处。 CUDA和Anaconda的关系 CUDA Toolkit是由Nvidia官方提供的完整工具包&#xff0c;其中提供了Nvidia驱动程序、开发CUDA程序相关的开发工具包等。 Anaconda在安装Pytorch等会用到的CUDA的框架时…...

0725,进程间传递文件描述符,socketpair + sendmsg/recvmsg

我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎…...

放大电路总结

补充: 只有直流移动时才有Rbe动态等效电阻 从RsUs看进去,实际上不管接了什么东西都能够看成是一个Ri(输入电阻) Ri Ui/Ii Rb//Rbe Ui/Us Ri/(RiRs) Aus (Uo/Ui)*(Ui/Us) Au *Ri/(RiRs) 当前面是一个电压源的信号 我们就需要输入电阻更大 Ro--->输出电阻--->将…...

深度学习1-简介

人工智能&#xff08;AI&#xff09;旨在打造模仿智能行为的系统。它覆盖了众多方法&#xff0c;涵盖了基于逻辑、搜索和概率推理的技术。机器学习是 AI 的一个分支&#xff0c;它通过对观测数据进行数学模型拟合来学习决策制定。这个领域近年来迅猛发展&#xff0c;现在几乎&a…...

Java基础语法 (基础介绍 二)

目录 Java 基础语法 第一个Java程序 基本语法 Java标识符 Java修饰符 Java变量 Java关键字 Java注释 Java 空行 Java 对象和类 Java中的对象 Java中的类 构造方法 创建对象 访问实例变量和方法 实例 源文件声明规则 Java包 Import语句 一个简单的例子 Java…...

SAPUI5基础知识18 - 自定义CSS和主题色

1. 背景 在上一篇博客中&#xff0c;我们通过使用SAPUI5提供的CSS类实现元素间距的调整。在本篇博客中&#xff0c;让我们看一下如何实现自定义的CSS样式。 2. 背景知识 2.1 CSS基础语法 CSS&#xff0c;全称为级联样式表&#xff08;Cascading Style Sheets&#xff09;&a…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!

目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...