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

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:

  1. Before the new interval: This phase processes all intervals that come entirely before the newInterval without overlapping.
  2. Merging overlapping intervals with the new interval: During this phase, any intervals that overlap with the newInterval are merged into a single interval.
  3. 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()&#xff1a;该方法将触摸事件分发给相应的视图或视图组。onInterceptTouchEvent()&#xff1a;该方法用于判断是否需要拦截触摸事件&#xff0c;如果需要拦截&#xff0c;则返回 true&#xff0c;否则返回 false。onTouchEvent()&a…...

[网络安全学习篇01]:windowsxp、windows2003、windows7、windows2008系统部署(千峰网络安全视频笔记)

VM 虚拟机&#xff1a;VMware Workstation 15.5 PRO&#xff08;建议升至最高版本&#xff09; 部署windows-xp系统 一、配置虚拟机硬件并安装系统 1、在VMware文件目录下创建一个空文件夹将其命名位&#xff1a;winxp-1 2、打开VMware软件&#xff0c;点击创建新的虚拟机。…...

CANoe自动化工程的搭建

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

第6章:支持向量机

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

ROS机器人启动move base时代价地图概率性无法加载的原因及解决方法

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

快速上手PyCharm指南

PyCharm简介 PyCharm是一种Python IDE&#xff08;Integrated Development Environment&#xff0c;集成开发环境&#xff09;&#xff0c;带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具&#xff0c;比如调试、语法高亮、项目管理、代码跳转、智能提示、自动…...

数字图像处理 - 图像处理结合机器学习的应用示例

在本文中,特别关注树叶分类机器学习技术的实现。我们的目标是演示如何利用机器学习算法来分析一系列叶子照片,从而实现准确分类并提供对植物领域有价值的算法。 图像处理中机器学习的本质 机器学习使计算机能够学习模式并根据视觉数据进行预测,彻底改变了图像处理领域。在叶…...

Linux命令200例:zip和unzip用于压缩和解压文件(常用)

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

通过 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的综合优先级。当选择下一个要遍历的节点时&#xff0c;总会选取综合优先级最高&#xff08;f(n)值最小&#xff0…...

postgresql 分类排名

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

TCP服务器实现—多进程版,多线程版,线程池版

目录 前言 1.存在的问题 2.多进程版 3.多线程版 4.线程池版 总结 前言 在上一篇文章中使用TCP协议实现了一个简单的服务器&#xff0c;可以用来服务端和客户端通信&#xff0c;但是之前的服务器存在一个问题&#xff0c;就是当有多个客户端连接服务器的时候&#xff0c;服…...

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&#xff1a;…...

AI夏令营第三期 - 基于论文摘要的文本分类与关键词抽取挑战赛笔记

赛题&#xff1a;基于论文摘要的文本分类与关键词抽取 背景&#xff1a;高效的从海量医学文献中提取疾病诊断和治疗关键信息 任务&#xff1a;通过论文摘要判断论文是否为医学文献 样例 数据集&#xff1a;csv文件&#xff0c;字段&#xff1a;标题、作者、摘要、关键词 评价指…...

使用qsqlmysql操作mysql提示Driver not loaded

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

Java云原生框架Quarkus初探

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

ElasticSearch相关概念

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

微服务实战项目-学成在线-项目部署

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

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...