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

无重叠区间-力扣435-java贪心策略

一、题目描述

给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]

输出: 1

解释: 移除 [1,3] 后,剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

来源:力扣(LeetCode)

链接:https://leetcode.cn/problems/non-overlapping-intervals

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、运行结果

三、解题思路

这里用的是贪心策略,刚好学习完贪心思想,树上有一道非常类似的题:活动选择。

大致思想就是:先将每个区间按结束时间(第二列)从小到大排列,首先选择第一个区间,然后将与其重叠的区间都移除掉,统计在该区间结束后开始的第一个区间(第一个不和前面的区间重叠的区间),重复进行选择,就可以得到最大不相交子集,总区间的个数减去最大不想交子集中区间的个数就是题目所求的个数。

四、AC代码

class Solution {public int eraseOverlapIntervals(int[][] intervals) {//取出最大不相交子集中区间的个数,总区间个数减去该数就是所求int n = intervals.length;Arrays.sort(intervals, new Comparator<int[]>(){  //按第二列(结束时间)对数组排序public int compare(int[] o1, int[] o2){if(o1[1] == o2[1])return o1[0]-o2[0];return o1[1] - o2[1];}});int count = 1, endTime = intervals[0][1];  for(int i=1; i<n; i++){if(intervals[i][0] >= endTime) {  //开始时间在前面的结束时间之后endTime = intervals[i][1];count++;}}return n-count;}
}

相关文章:

无重叠区间-力扣435-java贪心策略

一、题目描述给定一个区间的集合 intervals &#xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量&#xff0c;使剩余区间互不重叠 。示例 1:输入: intervals [[1,2],[2,3],[3,4],[1,3]]输出: 1解释: 移除 [1,3] 后&#xff0c;剩下的区间没有重叠。…...

Python使用VTK对容积超声图像进行体绘制(三维重建)

目录VTK简介什么是体绘制&#xff1f;体绘制效果图流程CodeQ&AReferenceVTK简介 VTK&#xff08;Visualization Toolkit&#xff09;是一个用于3D计算机图形学、图像处理和可视化的开源软件包。它包括一组C类和工具&#xff0c;可以让用户创建和处理复杂的3D图形和数据可视…...

JAVA设计模式之工厂模式讲解

目录 前言 开始表演 前言 Java中使用工厂模式的主要原因是为了实现代码的灵活性和可维护性。工厂模式是一种创建型设计模式&#xff0c;它提供了一种将对象的创建和使用进行分离的方式。具体来说&#xff0c;工厂模式可以将对象的创建过程封装在一个独立的工厂类中&#xff…...

近万字概述L3及以上自动驾驶故障运行和故障安全机制

本文描述了对ADS的FO和FS机制的评估方法。当系统不能按预期运行时,ADS将使用FO和FS机制。这些机制使ADS能够在最大程度上达到使车辆及其乘员脱离危险的MRC。定义、测试和验证实现MRC的FO和FS策略是确保ADS安全运行和部署的重要步骤。 MRC在SAE J3016中被定义为: 用户或ADS在…...

kafka入门到精通

文章目录一、kafka概述&#xff1f;1.定义1.2消息队列1.2.1 传统消息队列的使用场景1.2.2 消息队列好处1.2.3 消息队列两种模式1.3 kafka基础架构二、kafka快速入门1.1使用docker-compose安装kafka1.2测试访问kafka-manager1.3 查看kafka版本号1.4 查看zookeeper版本号1.5 扩展…...

es-09模糊查询

模糊查询 前缀搜索&#xff1a;prefix 概念&#xff1a;以xx开头的搜索&#xff0c;不计算相关度评分。 注意&#xff1a; 前缀搜索匹配的是term&#xff0c;而不是field。前缀搜索的性能很差前缀搜索没有缓存前缀搜索尽可能把前缀长度设置的更长 语法&#xff1a; GET <ind…...

57 - 深入解析任务调度

---- 整理自狄泰软件唐佐林老师课程 文章目录1. 问题1.1 思考1.2 实例分析&#xff1a;问题分析及解决2. 深入讨论2.1 任务调度的定义2.2 关于调度算法的分类2.3 什么时候进行任务调度2.4 任务的分类2.5 关于优先级调度2.6 问题2.7 调度算法的终极目标2.8 课后扩展1. 问题 系统…...

CAN总线开发一本全(3) - 微控制器集成的FlexCAN外设

CAN总线开发一本全&#xff08;3&#xff09; - 微控制器集成的FlexCAN外设 苏勇&#xff0c;2023年2月 文章目录CAN总线开发一本全&#xff08;3&#xff09; - 微控制器集成的FlexCAN外设引言硬件外设模块系统概要总线接口单元 - 寄存器清单数据结构 - 消息缓冲区MB初始化过…...

Elasticsearch7.8.0版本进阶——段合并

目录一、段的概述1.1、段的概念1.2、段的缺点1.3、如何解决段数量暴增问题二、段合并的流程三、段合并的注意事项一、段的概述 1.1、段的概念 每一 段 本身都是一个倒排索引。 1.2、段的缺点 由于自动刷新流程每秒会创建一个新的段 &#xff0c;这样会导致短时间内的段数量…...

Java版贪食蛇游戏

技术&#xff1a;Java等摘要&#xff1a;近年来Java作为一种新的编程语言&#xff0c;以其简单性、可移植性和平台无关性等优点&#xff0c;得到了广泛地应用&#xff0c;特别是Java与万维网的完美结合&#xff0c;使其成为网络编程和嵌入式编程领域的首选编程语言。MyEclipse是…...

2023年度数学建模竞赛汇总

本人7年数学建模竞赛经验&#xff0c;历史获奖率百分之百。团队成员都是拿过全国一等奖的硕博&#xff0c;有需要数模竞赛帮助的可以私信我。 下面主要列几年一些比较有含金量的数学建模竞赛&#xff08;按比赛时间顺序&#xff09; 1. 美国大学生数学建模竞赛 报名时间&…...

了解Python语言和版本

1.1 任务1了解Python语言和版本 Python 语言的名字来自于一个著名的电视剧"Monty Pythons Flying Cireus",Python之父 Guido van Rossum是这部电视剧的狂热爱好者&#xff0c;所以把他设计的语言命名为Python。 Python 是一门跨平台、开源、免费的解释型高级动态编…...

nvm (node版本管理工具)安装的详细步骤,并解决安装过程中遇到的问题

1、下载NVM&#xff0c;跳转下载链接后&#xff0c;如下图&#xff0c;下载红框后解压文件 2、安装 注意&#xff1a;双击安装之后&#xff0c;会有两个地址选择&#xff0c; 1、地址中不能存在空格 2、不要放在C盘中&#xff0c;后面需要改个设置文件&#xff0c;安装到C盘的…...

朴素贝叶斯笔记

贝叶斯公式在A 条件成立下&#xff0c;B的概率等于B的概率*在B条件成立下&#xff0c;A的概率/A的概率&#xff0c;推导假设一个学校中男生占总数的60%&#xff0c;女生占总数的40%。并且男生总是穿长裤&#xff0c;女生则一半穿长裤、一半穿裙子。1.正向概率。随机选取一个学生…...

【GUI】用于电动助力车性能分析的GUI(Matlab代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

Android:反编译apk踩坑/apktool/dex2jar/JDGUI

需求描述 想要反编译apk文件&#xff0c;搜到了这篇博客&#xff1a;Android APK反编译就这么简单 详解&#xff08;附图&#xff09;&#xff0c;非常有参考价值~但其中的工具下载链接都已404&#xff0c;而本杂鱼实际操作的过程中也出现了亿点点点点点点的问题&#xff0c;于…...

React 跨域的配置

1、为什么会出现跨域&#xff1f; 浏览器遵循同源政策&#xff08;同源策略三要素&#xff1a;协议相同、域名相同、端口相同&#xff09; 2、配置跨域代理 使用中间件 http-proxy-middleware&#xff08;安装依赖&#xff09; npm install http-proxy-middleware 创建setupP…...

Elasticsearch7.8.0版本进阶——持久化变更

目录一、持久化变更的概述二、事务日志&#xff08;translog&#xff09;三、持久化变更完整流程四、事务日志&#xff08;translog&#xff09;的作用五、事务日志&#xff08;translog&#xff09;的目的一、持久化变更的概述 没有用 fsync 把数据从文件系统缓存刷&#xff…...

CF Edu 127 A-E vp补题

CF Edu 127 A-D vp补题 继续每日一vp&#xff0c;今天晚上有课&#xff0c;时间不太多&#xff0c;回去就直接vp。前三题比较简单&#xff0c;过了之后排名rk2000&#xff0c;然后就去洗澡了。d题没怎么认真思考&#xff0c;其实也可做。最后rk4000。发挥还行&#xff0c;b题罚…...

剑指 Offer 05. 替换空格

摘要 剑指 Offer 05. 替换空格 一、字符替换 由于每次替换从1个字符变成3个字符&#xff0c;使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的3倍&#xff0c;这样可保证字符数组可以容纳所有替换后的字符。 获得 s 的长度 length创建字符数组 array&#x…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...