当前位置: 首页 > 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、每个模块的开发人员…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...