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

57. 插入区间(C++题解)

57. 插入区间

插入区间
给你一个无重叠的 ,按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例 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] 重叠。

示例 3:

输入:intervals = [], newInterval = [5,7]
输出:[[5,7]]

示例 4:

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

示例 5:

输入:intervals = [[1,5]], newInterval = [2,7]
输出:[[1,7]]

提示:

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

思路

最开始的思路就是,先把新的区间按照起点的顺序插入到旧区间内,之后对所有区间进行判断,来将可以合并的区间合并起来。但是如果直接这样做的话,因为插入的时候需要将所有元素后移一位,而对于区间合并,每次合并后都需要删除一个元素,导致每次需要将所有元素前移一位,这样的在后面测试案例较大的时候是没法通过的。因此需要别的思路来解决这几个问题。 除此之外,还需要知道,有两个区间(a,b),(c,d),当发现c<b的时候,说明两个区间需要合并。并且合并后的区间是(a,max(b,d))。

解题方法

创建一个ans来保存最后的区间列表,第一步,将新的区间插入到旧区间内,这里采用,遍历旧区间intervals,通过判断newInterval的起点大小,把小于newInterval起点的区间放进ans中,当发现不满足的时候,就是该放入newInterval的位置了,这个时候就可以把newInterval加入ans中。这样就做到了将newInterval插入到旧区间内。 第二步,进行判断新插入的区间newInterval是否需要合并,与ans中最后一个区间进行判断(此时newInterval还没有插入ans中),如果需要合并那么直接合并就行了,也就不需要newInterval插入了。 第三步,在把新的区间newInterval放入(包括合并)后,就需要把intervals剩下的区间加入ans中了,不过在加入的时候需要进行判断,如果需要合并,那么直接合并。如果不需要合并,只需要加入剩下的区间了。 第四步,在第三步之前,考虑了一个特殊情况,也就是新区间是是放入最后一个位置,这个时候需要单独把newInterval放入ans后,并且判断是否需要合并。

复杂度

时间复杂度:
O(n)

空间复杂度:
O(n)

Code

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>> ans;if(intervals.size()==0){intervals.push_back(newInterval);return intervals;}int i=0,k=0;//找到新区间应该放置在旧区间的位置for(;i<intervals.size();++i){if(newInterval[0]<=intervals[i][0]){if(i>0&&newInterval[0]<=intervals[i-1][1]){ans[i-1][1]=max(ans[i-1][1],newInterval[1]);k=i-1;}else{k=i;ans.push_back(newInterval);}break;}ans.push_back(intervals[i]);}//如果新的区间放在最后一个位置if(i==intervals.size()){if(newInterval[0]<=intervals[i-1][1]){ans[i-1][1]=max(ans[i-1][1],newInterval[1]);}else{ans.push_back(newInterval);}}//新的区间放在了旧区间中for(;i<intervals.size();++i){if(ans[k][1]>=intervals[i][0]){ans[k][1]=max(ans[k][1],intervals[i][1]);}else{ans.push_back(intervals[i]);}}return ans;}
};

相关文章:

57. 插入区间(C++题解)

57. 插入区间 插入区间 给你一个无重叠的 &#xff0c;按照区间起始端点排序的区间列表。 在列表中插入一个新的区间&#xff0c;你需要确保列表中的区间仍然有序且不重叠&#xff08;如果有必要的话&#xff0c;可以合并区间&#xff09;。 示例 1&#xff1a; 输入&#x…...

【数据结构Java版】 初识泛型和包装类

目录 1.包装类 1.1基本数据类型以及它们所对应的包装类 1.2装箱和拆箱 1.3自动装箱和自动拆箱 2.什么是泛型 3.引出泛型 4.泛型类的使用 4.1语法 4.2示例 4.3类型推导 5.泛型是如何编译的 5.1擦除机制 5.2正确的写法 6.泛型的上届 6.1语法 6.2示例 …...

Spring中如何解决循环依赖问题的三种方法

什么是循环依赖问题 在 Spring 中&#xff0c;循环依赖问题指的是两个或多个 bean 之间相互依赖形成的闭环。具体而言&#xff0c;当 bean A 依赖于 bean B&#xff0c;同时 bean B 也依赖于 bean A&#xff0c;就形成了循环依赖。 循环依赖问题在 Spring 容器中是一个非常常…...

【ArcGIS Pro二次开发】(65):进出平衡SHP转TXT、TXT转SHP

最近一个小伙伴提了这么一个需求&#xff0c;需要把TXT和SHP进行互转。 这种TXT文件其实遇到了好几个版本&#xff0c;都有一点小差异。之前已经做过一个TXT转SHP的工具&#xff0c;但好像不适用。于是针对这个版本&#xff0c;做了互转的2个工具。 【SHP转TXT】 一、要实现的…...

Shell开发实践:服务器的磁盘、CPU、内存的占用监控

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;CSDN领军人物&#xff0c;全栈领域优质创作者✌&#xff0c;CSDN博客专家&#xff0c;阿里云社区专家博主&#xff0c;2023年6月CSDN上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师…...

超详细 async和await 项目实战运用(附加文字解答+源码)

文章目录 问题描述async什么是 asyncasync 的作用async 的应用场景async 优点 await什么是 awaitawait 的作用await 的应用场景await 的优点async和 await结合使用 结束语 大家好&#xff01;又到了愉快的周末假期&#xff0c;今天是2023年9月3日|农历七月十九&#xff0c;我最…...

Maven入门教程(三):Maven语法

视频教程&#xff1a;Maven保姆级教程 Maven入门教程(一)&#xff1a;安装Maven环境 Maven入门教程(二)&#xff1a;idea/Eclipse使用Maven Maven入门教程(三)&#xff1a;Maven语法 Maven入门教程(四)&#xff1a;Nexus私服 Maven入门教程(五)&#xff1a;自定义脚手架 6.Mav…...

C++技术点,故事解析

语言的魅力 从人类诞生开始 &#xff0c;南方古猿到现代人类经历了非常多变化&#xff1b; 南方古猿到能人 有什么变化&#xff1f; 能人会使用工具&#xff0c;由于会使用工具 就可以获得肉类食物&#xff0c;当然只能吃一些动物腐肉 直到进化成直立人的晚期&#xff0c;在东…...

数据结构(Java实现)-字符串常量池与通配符

字符串常量池 在Java程序中&#xff0c;类似于&#xff1a;1&#xff0c; 2&#xff0c; 3&#xff0c;3.14&#xff0c;“hello”等字面类型的常量经常频繁使用&#xff0c;为了使程序的运行速度更快、更节省内存&#xff0c;Java为8种基本数据类型和String类都提供了常量池。…...

python强化学习--gym安装与使用

最近开始学习强化学习&#xff0c;第一步肯定是要学会安装和使用pym&#xff0c;原本以为很简单&#xff0c;事实上确实很简单&#xff0c;但是遇到一个小问题&#xff0c;就是安装gym之后&#xff0c;在应用的过程中&#xff0c;游戏界面没有显示出来&#xff0c;了解后才知道…...

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返回其根节点。 思路&#xff1a;题目给出了先序遍历和中序遍历的结果&#xff0c;因为先序遍历遵循根–>左–>…...

(第六天)初识Spring框架-SSM框架的学习与应用(Spring + Spring MVC + MyBatis)-Java EE企业级应用开发学习记录

SSM框架的学习与应用(Spring Spring MVC MyBatis)-Java EE企业级应用开发学习记录&#xff08;第六天&#xff09;初识Spring框架 ​ 昨天我们已经把Mybatis框架的基本知识全部学完&#xff0c;内容有Mybatis是一个半自动化的持久层ORM框架&#xff0c;深入学习编写动态SQL&a…...

如何使用『Nginx』配置后端『HTTPS』协议访问

前言 本篇博客主要讲解如何使用 Nginx 部署后端应用接口 SSL 证书&#xff0c;从而实现 HTTPS 协议访问接口&#xff08;本文使用公网 IP 部署&#xff0c;读者可以自行替换为域名&#xff09; 申请证书 须知 请在您的云服务平台申请 SSL 证书&#xff0c;一般来说证书期限…...

Git仓库简介

1、工作区、暂存区、仓库 工作区&#xff1a;电脑里能看到的目录。 暂存区&#xff1a;工作区有一个隐藏目录.git&#xff0c;是Git的版本库&#xff0c;Git的版本库里存了很多东西&#xff0c;其中最重要的就是称为stage&#xff08;或者叫index&#xff09;的暂存区&#xf…...

TensorRTC++ | INT8量化

Int8量化步骤 // 这是基本需要的组件 auto builder = make_nvshared(nvinfer1::createInferBuilder(logger)); auto config = make_nvshared(builder->createBuilderConfig())...

VS + qt环境使用QCustomPlot等三方库如何配置

文章目录 前言VS环境下引入第三方类库QCustomPlot方法一&#xff1a;解决办法&#xff1a; C中.dll与.lib文件的生成与使用1. 两种库&#xff1a;2.两种文件的区别 前言 Qt提供了显式和隐式导入第三方库方法&#xff0c;本文只介绍显示导入方法。 一般的第三方提供的库文件包…...

OS 段页结合的实际内存管理

虚拟内存承接段和页&#xff0c;从用户角度&#xff0c;虚拟内存提供段&#xff0c;从硬件角度&#xff0c;虚拟内存把段打散映射到页 先基于段的翻译&#xff0c;再基于页的翻译 p是pcb跟着进程换&#xff0c;64M一个段&#xff0c;set base就是建段表 因为每个进程虚拟地址…...

一种改进多旋翼无人机动态仿真的模块化仿真环境研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

02-请解释一下Java的内存模型和happens-before规则?【Java面试题总结】

请解释一下Java的内存模型和happens-before规则&#xff1f; 概念&#xff1a;Java内存模型&#xff0c;简称JMM&#xff0c;是一种定义了多线程程序中内存访问行为的规范。它定义了线程如何与主内存和工作内存进行交互&#xff0c;以及如何保证多线程程序的正确性和可见性。J…...

PVE 8 出现CPU 100% 冻结(卡死)

最近在研究PVE&#xff0c;然后下载官方最新版本系统8.x安装好后出现卡死问题&#xff0c;就连开个软件CPU也能飙到100%&#xff0c;开始我以为是硬件问题可能是资源不够&#xff0c;但是将系统切换回裸机&#xff08;不用PVE启动&#xff09;一点问题也没有&#xff0c;后来逐…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...