LeetCode 57—— 插入区间

阅读目录

    • 1. 题目
    • 2. 解题思路
    • 3. 代码实现

1. 题目

2. 解题思路

第一步,我们先寻找新区间和原始区间列表的重叠部分。

假设新区间为 [ x 1 , x 2 ] [x_1, x_2] [x1,x2],原始区间列表中的其中一个区间为 [ y 1 , y 2 ] [y_1, y_2] [y1,y2],那么如果两个区间不存在重叠的话,如上图所示,当且仅当:

x 2 < y 1   ∣ ∣   y 2 < x 1 x_2 < y_1 \space || \space y_2 < x_1 x2<y1 ∣∣ y2<x1

其它情况下,两个区间都会存在重叠,而重叠后的新区间有:

x 1 n e w = m i n ( x 1 , y 1 ) x^{new}_1 = min(x_1, y_1) x1new=min(x1,y1)
x 2 n e w = m a x ( x 2 , y 2 ) x^{new}_2 = max(x_2, y_2) x2new=max(x2,y2)

因此,我们首先遍历一遍原始区间列表,如果某个区间和新区间不重叠,我们直接添加这个区间到结果区间列表中去,如果某个区间和新区间存在重叠,那么我们更新重叠区间

然后,我们遍历结果区间列表,将重叠区间插入到合适的位置即可。

时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( n ) O(n) O(n)

3. 代码实现

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int> > new_intervals;
        for (size_t i = 0; i < intervals.size(); ++i) {
            // 和新区间不重叠,直接插入到结果中去
            if (newInterval[1] < intervals[i][0] || intervals[i][1] < newInterval[0]) {
                new_intervals.push_back(intervals[i]);
            } 
            // 和新区间有重叠,更新重叠区间
            else {
                newInterval[0] = min(intervals[i][0], newInterval[0]);
                newInterval[1] = max(intervals[i][1], newInterval[1]);
            }
        }
        
        if (new_intervals.empty()) {
            new_intervals.push_back(newInterval);
        } else {
            // 寻找新区间的插入位置
            for (size_t i = 0; i < new_intervals.size(); ++i) {
            	// 比某个区间的起始位置小,插入到这个区间前面
                if (newInterval[1] < new_intervals[i][0]) {
                    new_intervals.insert(new_intervals.begin()+i, newInterval);
                    break;
                } // 插入到最后面
                else if (i == new_intervals.size()-1 && newInterval[0] > new_intervals[i][1]) {
                    new_intervals.push_back(newInterval);
                }
            }
        }
        return new_intervals;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/543785.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PostgreSQL入门到实战-第三十弹

PostgreSQL入门到实战 PostgreSQL教程网站官网地址PostgreSQL概述更新计划 PostgreSQL教程网站 https://www.postgresqltutorial.com/ 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不一定100%复现, 还要以官方信息为准 https://www.postgresql.org/PostgreS…

【数据工具】ArcGIS批量出图工具箱

工具下载链接&#xff1a;数据下载链接 我们在使用Arcgis制图的过程中&#xff0c;经常会遇到需要大量出图的情况&#xff0c;如何将做好的图批量导出jpg是一件令人头疼的问题。 今天小编就给大家分享俩个ArcGIS批量出图的工具箱&#xff0c;一个可以批量导出图层为jpg&#…

运筹说 第112期 | M/M/s等待制排队模型

通过上期学习&#xff0c;大家已经了解了排队论中的一些基本概念&#xff0c;以及生灭过程和Poisson过程。 那么本期小编将基于这些基本原理&#xff0c;为大家介绍M/M/s混合制排队模型&#xff0c;包括单服务台模型和多服务台模型&#xff0c;介绍模型的概念以及推导过程等内容…

PoE 技术

1 PoE 技术产生背景 随着 WLAN 、 VoIP 、网络视频监控等新业务的飞速发展,大量的无线 LAN 访问点、 IP 电话、 IP 网络摄像头等基于 IP 的终端出现在工业现场。这些设备通常数量众多、位置特殊 、 布线复杂、设备取电困难,其实施部署不仅消耗大量人力物力,…

【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

目录 搜索算法&#xff08;深度优先搜索DFS和广度优先搜索BFS&#xff09;以及典型算法例题深度优先搜索 &#xff08;Depth First Search 简称 DFS&#xff09;DFS 的设计步骤深度优先搜索&#xff08;DFS&#xff09;算法例题例题一&#xff1a;N皇后问题例题二&#xff1a;路…

FreeRTOS学习 -- FreeRTOSConfig.h介绍

一、FreeRTOSConfig.h文件 FreeRTOS 的系统配置文件为 FreeRTOSConfig.h&#xff0c;在此配置文件中可以完成 FreeRTOS 的裁剪和配置。 FreeRTOS 的配置基本是通过在 FreeRTOSConfig.h 中使用“#define”这样的语句来定义宏定义实现的。在 FreeRTOS 的官方 demo 中&#xff0…

CentOS7离线升级OpenSSH_8.8p1

一、环境 centos7.9,升级openssh到8.8p1最新版本 二、下载升级包 # openssl和zlib为相关依赖 wget https://cdn.openbsd.org/pub/OpenBSD/OpenSSH/portable/openssh-8.8p1.tar.gz wget https://www.openssl.org/source/openssl-1.1.1j.tar.gz wget http://www.zlib.net/zl…

mysql dll文件的缺失和Can‘t connect to MySQL server on ‘localhost‘ (10061)

个人笔记&#xff08;整理不易&#xff0c;有帮助&#xff0c;收藏点赞评论&#xff0c;爱你们&#xff01;&#xff01;&#xff01;你的支持是我写作的动力&#xff09; 笔记目录&#xff1a;学习笔记目录_pytest和unittest、airtest_weixin_42717928的博客-CSDN博客 个人随笔…

数学:人工智能学习之路上的“拦路虎”及其背后的奥秘

在人工智能的浪潮席卷全球的今天&#xff0c;越来越多的人开始涉足这一领域&#xff0c;以期掌握其核心技术&#xff0c;为未来的科技发展贡献力量。然而&#xff0c;在学习的道路上&#xff0c;许多人却遇到了一个不小的挑战——数学。为何数学会成为学习人工智能的“拦路虎”…

js学习总结

这里写目录标题 前情提要JavaScript书写位置1. 内部javaScript (不常用)2. 外部javaScript (常用)3.内联javaScript (常用) js中的输入和输出输出语法1. document.write()2. alert()3. console.log() 输入语法prompt() 前情提要 1. 在javaScript中的 分号 是可以省略的JavaScr…

rocketmq面试

broker主从复制机制 同步复制&#xff1a; 等Master和Slave均写成功后&#xff0c;才反馈给客户端写成功状态&#xff1b; 如果Master出故障&#xff0c; Slave上有全部的备份数据&#xff0c;容易恢复&#xff0c;但是同步复制会增大数据写入延迟&#xff0c;降低系统吞吐量。…

SMS垃圾短信识别项目

注意&#xff1a;本文引用自专业人工智能社区Venus AI 更多AI知识请参考原站 &#xff08;[www.aideeplearning.cn]&#xff09; 项目背景 随着数字通信的快速发展&#xff0c;垃圾短信成为了一个普遍而烦人的问题。这些不请自来的消息不仅打扰了我们的日常生活&#xff0c;…

视频基础学习六——视频编码基础三(h264框架配合图文+具体抓包分析 万字)

系列文章目录 视频基础学习一——色立体、三原色以及像素 视频基础学习二——图像深度与格式&#xff08;RGB与YUV&#xff09; 视频基础学习三——视频帧率、码率与分辨率 视频基础学习四——视频编码基础一&#xff08;冗余信息&#xff09; 视频基础学习五——视频编码基础…

Redis漏洞利用

未授权 可以利用超级弱口令工具来判断redis是否能未授权登录 telnet #尝试登录info #查看redis信息 RCE方法 写shell 需要写权限需要知道web网站路径 config set dir /var/www/html config set dbfilename redis.php set test "<?php phpinfo(); ?>" sa…

低成本,高效能:探索物联网新宠LoRa

LoRa是什么&#xff1f; LoRa是一种物联网无线传输技术&#xff0c;利用调制解调器实现低功耗远距离数据传输。其基本工作原理是通过基站发送数据到特定终端设备&#xff0c;实现双向数据传输。 LoRa无线传输技术是一种为低功耗和低成本设计的无线技术&#xff0c;用于实现远距…

mybatis的使用技巧7——mysql中in,exists,join的用法和区别

在实际项目开发中&#xff0c;sql查询中的连表查询和子查询用的是最多的&#xff0c;但是很多人对于in&#xff0c;exists&#xff0c;join的用法认识不足&#xff0c;随意运用&#xff0c;这种情况如果在大数据量查询时&#xff0c;会存在很大的隐患。 一.子查询&#xff08;…

transformer入门知识解析——新手必看

对应课程&#xff1a;Transformer简明教程, 从理论到代码实现到项目实战, NLP进阶必知必会._哔哩哔哩_bilibili 1.初识transformer结构 transformer的结构&#xff1a; 编码器解码器的内部结构&#xff1a; Self Attention 表示自注意力机制 Feed Forward 表示全连接层 2.计算…

45.HarmonyOS鸿蒙系统 App(ArkUI)创建列表(List)

列表是一种复杂的容器&#xff0c;当列表项达到一定数量&#xff0c;内容超过屏幕大小时&#xff0c;可以自动提供滚动功能。它适合用于呈现同类数据类型或数据类型集&#xff0c;例如图片和文本。在列表中显示数据集合是许多应用程序中的常见要求&#xff08;如通讯录、音乐列…

springBoot+vue编程中使用mybatis-plus遇到的问题

mybatis-plus中遇到的问题Code Companion Servlet.service() for servlet [dispatcherServlet] in context with path [] threw exception [Request processing failed; nested exception is org.apache.ibatis.binding.BindingException: Invalid bound statement (not found)…

如何正确使用数字化仪前端信号调理?(一)

一、前言 板卡式的数字转换器和类似测量仪器&#xff0c;比如图1所示的德思特TS-M4i系列&#xff0c;都需要为各种各样的特性信号与内部模数转换器&#xff08;ADC&#xff09;的固定输入范围做匹配。 图1&#xff1a;德思特TS-M4i系列高速数字化仪&#xff0c;包括2或4通道版…