LeetCode //C - 57. Insert Interval
57. Insert Interval
You are given an array of non-overlapping intervals intervals where intervals[i] = [ s t a r t i , e n d i start_i, end_i starti,endi] represent the start and the end of the i t h i^{th} ith interval and intervals is sorted in ascending order by s t a r t i start_i starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by s t a r t i start_i starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Constraints:
- 0 < = i n t e r v a l s . l e n g t h < = 1 0 4 0 <= intervals.length <= 10^4 0<=intervals.length<=104
- intervals[i].length == 2
- 0 < = s t a r t i < = e n d i < = 1 0 5 0 <= start_i <= end_i <= 10^5 0<=starti<=endi<=105
- intervals is sorted by starti in ascending order.
- newInterval.length == 2
- 0 < = s t a r t < = e n d < = 1 0 5 0 <= start <= end <= 10^5 0<=start<=end<=105
From: LeetCode
Link: 57. Insert Interval
Solution:
Ideas:
The main idea behind the code is to break down the insertion process into three primary segments:
- Before the new interval: This phase processes all intervals that come entirely before the newInterval without overlapping.
- Merging overlapping intervals with the new interval: During this phase, any intervals that overlap with the newInterval are merged into a single interval.
- After the new interval: This phase processes all intervals that come entirely after the newInterval without overlapping.
1. Before the new interval:
In this phase, the algorithm checks all intervals that are entirely before the newInterval. This is determined by checking if the end of the current interval is less than the start of the newInterval. All such intervals are directly added to the result because they won’t overlap with the newInterval.
2. Merging overlapping intervals with the new interval:
In this phase, the algorithm checks for any intervals that overlap with the newInterval. An overlap is determined if the start of the current interval is less than or equal to the end of the newInterval. For each overlapping interval, the start of the merged interval becomes the minimum of the current interval’s start and the newInterval’s start. Similarly, the end of the merged interval becomes the maximum of the current interval’s end and the newInterval’s end.
3. After the new interval:
Post merging, all intervals that come entirely after the merged newInterval are added to the result as they are, because they won’t have any overlap with the newInterval.
In the end, the function updates the returnSize to indicate the number of intervals in the result, and returnColumnSizes is updated to indicate the size of each interval (which is always 2). The result is then returned.
Code:
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes){// Initializationsint** res = (int**)malloc(sizeof(int*) * (intervalsSize + 1)); // +1 in case we don't merge and just insert the new intervalint* colSizes = (int*)malloc(sizeof(int) * (intervalsSize + 1));int index = 0, resIndex = 0;// Before the new intervalwhile(index < intervalsSize && intervals[index][1] < newInterval[0]){res[resIndex] = intervals[index];colSizes[resIndex] = 2;resIndex++;index++;}// Merge overlapping intervals with new intervalwhile(index < intervalsSize && intervals[index][0] <= newInterval[1]){newInterval[0] = fmin(newInterval[0], intervals[index][0]);newInterval[1] = fmax(newInterval[1], intervals[index][1]);index++;}// Add the merged new intervalint* mergedInterval = (int*)malloc(sizeof(int) * 2);mergedInterval[0] = newInterval[0];mergedInterval[1] = newInterval[1];res[resIndex] = mergedInterval;colSizes[resIndex] = 2;resIndex++;// After the new intervalwhile(index < intervalsSize){res[resIndex] = intervals[index];colSizes[resIndex] = 2;resIndex++;index++;}// Set return sizes*returnSize = resIndex;*returnColumnSizes = colSizes;return res;
}
相关文章:
LeetCode //C - 57. Insert Interval
57. Insert Interval You are given an array of non-overlapping intervals intervals where intervals[i] [ s t a r t i , e n d i start_i, end_i starti,endi] represent the start and the end of the i t h i^{th} ith interval and intervals is sorted in asce…...
android手势事件
与手势事件有关的方法 dispatchTouchEvent():该方法将触摸事件分发给相应的视图或视图组。onInterceptTouchEvent():该方法用于判断是否需要拦截触摸事件,如果需要拦截,则返回 true,否则返回 false。onTouchEvent()&a…...
[网络安全学习篇01]:windowsxp、windows2003、windows7、windows2008系统部署(千峰网络安全视频笔记)
VM 虚拟机:VMware Workstation 15.5 PRO(建议升至最高版本) 部署windows-xp系统 一、配置虚拟机硬件并安装系统 1、在VMware文件目录下创建一个空文件夹将其命名位:winxp-1 2、打开VMware软件,点击创建新的虚拟机。…...

CANoe自动化工程的搭建
基于XMLCAPL建立自动化工程 1、导入ini文件2、新建 Test Environment3、报告类型4、代码编写 1、导入ini文件 工程的配置的文件,配置DUT相关信息,具体视工程而编写内容。 2、新建 Test Environment 1、新建XML测试用例环境 2、导入XML测试用例文件 …...

第6章:支持向量机
间隔与支持向量 w为法向量,决定的是超平面的方向。b是偏移项,决定了超平面与原点之间的距离。 为什么最大化间隔,得到的就是最优平面呢? 当超平面没有正确划分正负样本时,几何间隔为负数。几何间隔,各个…...

ROS机器人启动move base时代价地图概率性无法加载的原因及解决方法
最近,使用ROS机器人,在启动move_base 节点时,概率性会出现全局和局部代价地图不加载的问题,此时,发布目标点也无法启动路径规划。而且该问题有时候出现概率很低,比如启动10次,会有1次发送该情况…...

快速上手PyCharm指南
PyCharm简介 PyCharm是一种Python IDE(Integrated Development Environment,集成开发环境),带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具,比如调试、语法高亮、项目管理、代码跳转、智能提示、自动…...
数字图像处理 - 图像处理结合机器学习的应用示例
在本文中,特别关注树叶分类机器学习技术的实现。我们的目标是演示如何利用机器学习算法来分析一系列叶子照片,从而实现准确分类并提供对植物领域有价值的算法。 图像处理中机器学习的本质 机器学习使计算机能够学习模式并根据视觉数据进行预测,彻底改变了图像处理领域。在叶…...

Linux命令200例:zip和unzip用于压缩和解压文件(常用)
🏆作者简介,黑夜开发者,全栈领域新星创作者✌。CSDN专家博主,阿里云社区专家博主,2023年6月csdn上海赛道top4。 🏆数年电商行业从业经验,历任核心研发工程师,项目技术负责人。 &…...

通过 HttpClient 发送请求
文章目录 1. 引入 maven 依赖2. 发送 GET 方式的请求3. 发送 POST 方式的请求 1. 引入 maven 依赖 <dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpclient</artifactId> </dependency>2. 发送 GET 方式的请求…...
管理类联考——逻辑——真题篇——按知识分类——汇总篇——一、形式逻辑——假言——第二节 必要条件假言+第三节 特殊假言
文章目录 第二节 必要条件假言命题-才真题(2018-26)-假言-必要假言-才-(1)建模-“才”-后推前。-(2)A→B的公式化转换-A→B的等价命题:①逆否命题:非B→非A。真题(2020-26)-假言-必要假言-才-(1)建模-“才”-后推前。-(2)A→B的公式化转换-A→B的等价命题:①逆…...

算法笔记:A*算法
A*算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度 1 中心思路 A*算法通过下面这个函数来计算每个节点n的优先级 f(n)g(n)h(n) f(n)是节点n的综合优先级。当选择下一个要遍历的节点时,总会选取综合优先级最高(f(n)值最小࿰…...

postgresql 分类排名
postgresql 分类排名 排名窗口函数示例CUME_DIST 和 NTILE 排名窗口函数 排名窗口函数用于对数据进行分组排名。常见的排名窗口函数包括: • ROW_NUMBER,为分区中的每行数据分配一个序列号,序列号从 1 开始分配。 • RANK,计算每…...

TCP服务器实现—多进程版,多线程版,线程池版
目录 前言 1.存在的问题 2.多进程版 3.多线程版 4.线程池版 总结 前言 在上一篇文章中使用TCP协议实现了一个简单的服务器,可以用来服务端和客户端通信,但是之前的服务器存在一个问题,就是当有多个客户端连接服务器的时候,服…...
Nginx 配置文件的完整指南 (二)
文章目录 四、反向代理配置4.1 proxy_pass效果1—路径重写效果2—转发到其他服务器 4.2 proxy_pass使用规则4.3 proxy_set_header4.3.1 修改请求协议 五、负载均衡配置5.1 upstream5.2 server5.3 负载均衡策略5.3.1 轮询5.3.2 加权轮询5.3.3 最少连接5.3.3 ip_hash:…...

AI夏令营第三期 - 基于论文摘要的文本分类与关键词抽取挑战赛笔记
赛题:基于论文摘要的文本分类与关键词抽取 背景:高效的从海量医学文献中提取疾病诊断和治疗关键信息 任务:通过论文摘要判断论文是否为医学文献 样例 数据集:csv文件,字段:标题、作者、摘要、关键词 评价指…...

使用qsqlmysql操作mysql提示Driver not loaded
环境: win10 IDE: qt creator 编译器: mingw32 这里简单的记录下。我遇到的情况是在IDE使用debug和release程序都是运行正常,但是当我编译成发布版本之后。老是提示Driver not load。 这就很奇诡了。 回顾了下编译的时候是需要在使用qt先编译下libqsqlmysql.dll的…...

Java云原生框架Quarkus初探
Java云原生框架Quarkus初探 Quarkus 介绍 Quarkus 是一个云原生,容器优先的Java应用框架,它号称是超音速和亚原子的框架,主要特点是构建速度、启动速度快和占用资源少等特点。它为OpenJDK HotSpot和GraalVM量身定制, 根据Java库和…...

ElasticSearch相关概念
文章目录 前提倒排索引MySQL、ES的区别和关联IK分词器索引库mapping属性索引库的crud 文档的crudRestClientDSL查询DSL 查询种类DSL query 基本语法 搜索结构处理排序分页高亮RestClient 前提 开源的搜索引擎,从海量数据中快速找到需要的内容。(分词检索…...

微服务实战项目-学成在线-项目部署
微服务实战项目-学成在线-项目部署 1 什么是DevOps 一个软件的生命周期包括:需求分析阶、设计、开发、测试、上线、维护、升级、废弃。 通过示例说明如下: 1、产品人员进行需求分析 2、设计人员进行软件架构设计和模块设计。 3、每个模块的开发人员…...

IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...