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

【算法与数据结构】435、LeetCode无重叠区间

文章目录

  • 一、题目
  • 二、解法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

  思路分析:思路和【算法与数据结构】452、LeetCode用最少数量的箭引爆气球类似,也是排序+找重叠区间。因为题目要求去掉重叠区间,所以要找挨着的重叠区间数量。因此在if语句中稍作修改。
  程序如下

class Solution {
static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];
}
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int result = 0;sort(intervals.begin(), intervals.end(), cmp);for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]){ // 如果第i个区间和第i-1个区间挨着,移除区间数+1result++;intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠区间最小右边界}}return result;}
};

复杂度分析:

  • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn),一个快速排序。
  • 空间复杂度: O ( 1 ) O(1) O(1),有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要O(n)的栈空间
    可以看出代码并不复杂。

三、完整代码

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;class Solution {
static bool cmp(const vector<int>& a, const vector<int>& b) {if (a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];
}
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int result = 0;sort(intervals.begin(), intervals.end(), cmp);for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]){ // 如果第i个区间和第i-1个区间挨着,移除区间数+1result++;intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠区间最小右边界}}return result;}
};int main() {vector<vector<int>> intervals = { {1, 2}, {2, 3},{3, 4},{1, 3} };Solution s1;int result = s1.eraseOverlapIntervals(intervals);cout << "结果:" << result << endl;system("pause");return 0;
}

end

相关文章:

【算法与数据结构】435、LeetCode无重叠区间

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a;思路和【算法与数据结构】452、LeetCode用最少数量的箭引爆气球类似&#xff0c;也是排序找重叠区间。…...

【开题报告】基于SpringBoot的茶文化宣传网站设计与实现

1.研究背景和意义 1.1研究背景 茶文化是中国传统文化的重要组成部分&#xff0c;具有悠久的历史和丰富的内涵。茶文化不仅是一种饮食文化&#xff0c;更是一种生活方式和精神追求。然而&#xff0c;在当今快节奏的生活中&#xff0c;茶文化逐渐被人们所忽视。为了加强对茶文化…...

用通俗易懂的方式讲解大模型:基于 Langchain 和 ChatChat 部署本地知识库问答系统

之前写了一篇文章介绍基于 LangChain 和 ChatGLM 打造自有知识库问答系统&#xff0c;最近该项目更新了0.2新版本&#xff0c;这个版本与之前的版本差别很大&#xff0c;底层的架构发生了很大的变化。 该项目最早是基于 ChatGLM 这个 LLM&#xff08;大语言模型&#xff09;来…...

YOLO训练results.csv文件可视化(原模型与改进模型对比可视化)

一、单独一个文件可视化&#xff08;源码对应utils文件夹下的plots.py文件的plot_results类&#xff09; from pathlib import Path import matplotlib.pyplot as plt import pandas as pd def plot_results(fileruns/train/exp9/results.csv, dir):# Plot training results.c…...

uni-appcss语法

锋哥原创的uni-app视频教程&#xff1a; 2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中..._哔哩哔哩_bilibili2023版uniapp从入门到上天视频教程(Java后端无废话版)&#xff0c;火爆更新中...共计23条视频&#xff0c;包括&#xff1a;第1讲 uni…...

java在线票务系统(选座)Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 java servlet 在线票务系统&#xff08;选座&#xff09;管理系统是一套完善的java web信息管理系统 系统采用serlvetdaobean&#xff08;mvc模式)&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要…...

Python 简易图形界面库easygui 对话框大全(续)

目录 EasyGUI库 主要特点 使用场景 对话框样式 10. 文件打开框 fileopenbox 11. 文件保存框 filesavebox 12. 目录打开框 diropenbox 13. 索引对话框 indexbox 14. 例外报告框 exceptionbox 15. 代码文本框 codebox 16. 密码输入框 passwordbox 17. 多重文本框 mul…...

电容器50ZLH56MEFC6.3X11

电容器 常用电子元器件类型 50ZLH56MEFC6.3X11 文章目录 电容器前言一、电容器二、50ZLH56MEFC6.3X11总结前言 电容器在电子电路中有许多重要的应用,如滤波、耦合、储能、定时等。不同类型的电容器具有不同的性能特点,例如电容量、工作电压、频率响应等。在选择和使用电容…...

vscode 支持c,c++编译调试方法

概述&#xff1a;tasks.jason launch.json settings.json一定要有&#xff0c;没有就别想跑。还有就是c 和c配置有区别&#xff0c;切记&#xff0c;下文有说 1.安装扩展插件。 2.安装编译器&#xff0c;gcc.我用的是x86_64-8.1.0-release-win32-seh-rt_v6-rev0.7z &#xf…...

MyBatis的缓存!!!!

为什么使用缓存&#xff1f; 首次访问时&#xff0c;查询数据库&#xff0c;并将数据存储到内存中&#xff1b;再次访问时直接访问缓存&#xff0c;减少IO、硬盘读写次数、提高效率 Mybatis中的一级缓存和二级缓存&#xff1f; 一级缓存: 它指的是mybatis中的SqlSession对象的…...

ToB还是ToC?工业级与消费级AR眼镜都能干什么?

随着科技的飞速发展&#xff0c;增强现实&#xff08;AR&#xff09;技术逐渐融入我们的日常生活。我国AR眼镜消费市场分为消费级和工业级应用。其中消费级主要分为游戏、影视、直播以及社交购物与旅游&#xff1b;工业级主要应用于医疗、汽车、工业、船舶、电力和仓储等专业领…...

设计模式-Java版本

文章目录 前言设计原则单一职责原则开闭原则里氏替换原则迪米特法则接口隔离原则依赖倒置原则 设计模式构建类型工厂模式抽象工厂建造者模式原型模式单例模式 结构型适配器模式桥接模式组合模式装饰器模式代理模式外观模式享元模式 行为模式责任链模式命令模式迭代器模式中介模…...

数据库中如何修改和删除字段

PS&#xff1a;在"[ ]"中的所有数据都是可修改的 添加表字段 ALTER TABLE [表名] add [添加的新字段名] [添加新的数据类型] COMMENT [昵称] alter&#xff1a;修改&#xff08;后面一般加table表示修改表&#xff09; add&#xff1a;添加一个字段 在这个里面c…...

在 Golang 应用程序中管理多个数据库

掌握在 Golang 项目中处理多个数据库的艺术 在当前软件开发领域中&#xff0c;处理单个应用程序内的多个数据库的需求越来越普遍。具有强大功能的 Golang 是处理此类任务的绝佳解决方案&#xff0c;无论您是与多个数据源合作还是仅为增强组织和可扩展性而分隔数据。在本文中&a…...

理解开源协议GPL、MIT、BSD、Apache License

开源协议是一种法律文件&#xff0c;规定了使用、修改和分享开源软件的规则和条件。以下是一些常见的开源协议及其相同点和区别&#xff1a;GPL&#xff08;GNU General Public License&#xff09;&#xff1a;GPL 是一种比较严格的开源协议&#xff0c;要求使用者如果对开源软…...

Talk | 北京大学博士生汪海洋:通向3D感知大模型的前置方案

本期为TechBeat人工智能社区第559期线上Talk。 北京时间12月28日(周四)20:00&#xff0c;北京大学博士生—汪海洋的Talk已准时在TechBeat人工智能社区开播&#xff01; 他与大家分享的主题是: “通向3D感知大模型的前置方案”&#xff0c;介绍了他的团队在3D视觉大模型的前置方…...

【C语言数组传参】规则详解

目录 数组传参介绍 数组传参规则 数组传参的实参 特殊情况一&#xff1a;sizeof&#xff08;数组名&#xff09; 特殊情况二&#xff1a;&数组名 数组传参的形参 数组传参使用数组名作为形参接收 形参如果是⼀维数组 形参如果是⼆维数组 数组传参使用指针作为形参…...

【Linux】Ubuntu22.04版本下实现gcc版本的快速切换

本文将介绍如何在Ubuntu22.04版本下实现gcc版本的快速切换。 本文首发于 ❄️慕雪的寒舍 前言 有的时候&#xff0c;不同版本的gcc会造成一些细微的差异&#xff0c;导致相关的一些工具不兼容&#xff0c;比如用于单元测试覆盖率生成的gcov/lcov工具&#xff0c;在不同的gcc版…...

使用Node Exporter采集主机数据

安装 Node Exporter 在 Prometheus 的架构设计中&#xff0c;Prometheus Server 并不直接服务监控特定的目标&#xff0c;其主要任务负责数据的收集&#xff0c;存储并且对外提供数据查询支持。因此为了能够能够监控到某些东西&#xff0c;如主机的 CPU 使用率&#xff0c;我们…...

Django 文件上传(十二)

当 Django 处理文件上传时&#xff0c;文件数据最终会被放置在 request.FILES 。 查看文档&#xff1a;文件上传 | Django 文档 | Django Django工程如下&#xff1a; 创建本地存储目录 在static/应用目录下创建uploads目录用于存储接收上传的文件 在settings.py 配置静态目…...

k8s的陈述式资源管理

k8s的陈述式资源管理&#xff1a; 命令行&#xff1a;kubectl命令行工具 优点&#xff1a;90%以上的场景都可以满足 对资源的增&#xff0c;删&#xff0c;查比较方便&#xff0c;对改不是很友好 缺点&#xff1a; 命令比较冗长&#xff0c;复杂&#xff0c;难记 声明式&…...

electron-builder 打包exe后白屏

项目用的是An Electron application with Vue3 and TypeScript。 Debug运行项目没问题&#xff0c;可以显示页面。不过有浏览器控制台显示错误&#xff1a; Unable to load preload script&#xff1a;preload/index.js Unable to load preload script 翻译后&#xff1a;无法…...

mvvm,vue双向数据绑定的原理

MVVM (Model-View-ViewModel) 是一种设计模式&#xff0c;主要用于构建用户界面。在 MVVM 中&#xff0c;Model 表示应用程序的数据&#xff0c;View 表示用户界面&#xff0c;而 ViewModel 是 Model 和 View 之间的连接器。MVVM 的核心思想是将视图与模型分离&#xff0c;使它…...

【Java中序列化的原理是什么(解析)】

&#x1f341;序列化的原理是什么&#xff1f; &#x1f341;典型-----解析&#x1f341;拓展知识仓&#x1f341;Serializable 和 Externalizable 接门有何不同? &#x1f341;如果序列化后的文件或者原始类被篡改&#xff0c;还能被反序列化吗?&#x1f341;serialVersionU…...

冠赢互娱基于 OpenKrusieGame 实现游戏云原生架构升级

作者&#xff1a;力铭 关于冠赢互娱 冠赢互娱是一家集手游、网游、VR 游戏等研发、发行于一体的游戏公司&#xff0c;旗下官方正版授权的传奇类手游——《仙境传奇》系列深受广大玩家们的喜爱。基于多年 MMORPG 类型游戏的自研与运营经验&#xff0c;冠赢互娱正式推出了 2D M…...

Mybatis 动态 SQL - trim, where, set

之前的例子都巧妙地避开了一个臭名昭著的动态SQL挑战。考虑一下如果我们回到之前的“if”例子&#xff0c;但这次我们将“ACTIVE 1”也作为一个动态条件。 <select id"findActiveBlogLike"resultType"Blog">SELECT * FROM BLOGWHERE<if test&qu…...

大模型系列:OpenAI使用技巧_使用OpenAI进行K-means聚类

文章目录 1. 使用K-means算法找到聚类2. 聚类中的文本样本和聚类的命名让我们展示每个聚类中的随机样本。 我们使用一个简单的k-means算法来演示如何进行聚类。聚类可以帮助发现数据中有价值的隐藏分组。数据集是在 Get_embeddings_from_dataset Notebook中创建的。 # 导入必要…...

共享单车之数据分析

文章目录 第1关&#xff1a;统计共享单车每天的平均使用时间第2关&#xff1a;统计共享单车在指定地点的每天平均次数第3关&#xff1a;统计共享单车指定车辆每次使用的空闲平均时间第4关&#xff1a;统计指定时间共享单车使用次数第5关&#xff1a;统计共享单车线路流量 第1关…...

Spring的Bean你了解吗

Bean的配置 Spring容器支持XML(常用)和Properties两种格式的配置文件 Spring中XML配置文件的根元素是,中包含了多个子元素&#xff0c;每个子元素定义了一个Bean,并描述了该Bean如何装配到Spring容器中 元素包含了多个属性以及子元素&#xff0c;常用属性及子元素如下所示 i…...

MongoDB聚合:$merge 阶段(1)

$merge的用途是把聚合管道产生的结果写入指定的集合&#xff0c;有时候可以用$merge来做物化视图。需要注意&#xff0c;$meger操作必须是聚合管道的最后一个阶段。具体功能有&#xff1a; 能够输出到当前或不同的数据库能够输出到正在聚合的集合&#xff08;慎重&#xff1a;…...

开源企业网站系统/专业网页设计和网站制作公司

原标题&#xff1a;[新手向视频]新版PyCharm创建项目为什么会有问题文字版之前我们发过一篇关于 PyCharm 的文章&#xff1a;喏&#xff0c;你们要的 PyCharm 快速上手指南文章帮好多新手解决了问题&#xff0c;在微博上还被知乎官方账号推荐了。而 PyCharm 在2017年的新版本中…...

什么网站可以自己接工程做预算/网站建设推广多少钱

数组小谈😁 庆哥: 嗨,小白,知道啥是数组吗?😎 小白: 你看你这话说的,数组那还不简单,学计算机的没有不知道数组的吧,我们刚开始接触C语言的时候就有数组啊,现在在学习java,也有数组啊,一般不就这样嘛😁 int[] array = new int[10]这就创建了一个长度为10的…...

内蒙网站开发/seo新手入门教程

第一版&#xff1a; # 拿到页面源代码 requests # 通过re来提取想要的有效信息 re # csv 数据存储 import requests import re import csv# 现在要提取名字&#xff0c;年份url "https://movie.douban.com/top250"headers {"User-Agent": "Mozilla…...

苏州做网站建设公司/最新的全国疫情

一、HTTP的缺点 到目前为止&#xff0c;我们已经介绍完HTTP&#xff0c;它具有相当优秀和方便的一面&#xff0c;但它也有不足之处&#xff0c;HTTP 主要有这些不足&#xff0c;例举如下。 通信使用明文&#xff08;不加密&#xff09;&#xff0c;内容可能会被窃听 不验证通…...

响应式网站设计的要求/小红书网络营销策划方案

文章目录1. Mybatis概述1.1 简介1.2 如何获得Mybatis1.3 持久化1.4 持久层1.5 为什么需要Mybatis1.6 Mybatis开发工作流程2 第一个Mybatis程序2.1 搭建环境2.2 创建一个模块2.3 编写代码2.4 测试本文章涉及环境版本&#xff1a; mysql 5.7Mybatis 3.5.xMaven 3.6.xJDK 1.8 项目…...

工商经营性网站备案/网站排名优化推广

现在华为主要是买不到手机的处理器芯片&#xff0c;所以理论上可以使用5G云计算的方式实现“云手机”&#xff0c;也就是将手机的计算功能放在远程服务器上&#xff0c;手机本身只作为联网和显示设备。这样一来即使手机没有处理器&#xff0c;也可以实现上网、打游戏等功能。其…...