当前位置: 首页 > 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 配置静态目…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...