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

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

.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 适用场…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...