452. 用最少数量的箭引爆气球[排序+贪心]

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=study-plan-v2&envId=top-interview-150

题目描述

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。

给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1:

输入:points = [[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:气球可以用2支箭来爆破:
-在x = 6处射出箭,击破气球[2,8]和[1,6]。
-在x = 11处发射箭,击破气球[10,16]和[7,12]。
示例 2:

输入:points = [[1,2],[3,4],[5,6],[7,8]]
输出:4
解释:每个气球需要射出一支箭,总共需要4支箭。
示例 3:

输入:points = [[1,2],[2,3],[3,4],[4,5]]
输出:2
解释:气球可以用2支箭来爆破:

  • 在x = 2处发射箭,击破气球[1,2]和[2,3]。
  • 在x = 4处射出箭,击破气球[3,4]和[4,5]。

思路分析

这个题目的思路是排序加贪心,乍一眼看上去怪异得很,离谱。
首先我们把这些气球的位置按照右侧边界大小排序。
在这里插入图片描述
如图 1-1 所示,我们随机射出一支箭,引爆了除红色气球以外的所有气球。我们称所有引爆的气球为「原本引爆的气球」,其余的气球为「原本完好的气球」。可以发现,如果我们将这支箭的射出位置稍微往右移动一点,那么我们就有机会引爆红色气球,如图 1-2 所示。

那么我们最远可以将这支箭往右移动多远呢?将这支箭的射出位置移动到这个右边界位置,这也是最远可以往右移动到的位置:如图 1-3 所示,只要我们再往右移动一点点,这个气球就无法被引爆了。

因此,我们可以断定:

一定存在一种最优(射出的箭数最小)的方法,使得每一支箭的射出位置都恰好对应着某一个气球的右边界。

这是为什么?我们考虑任意一种最优的方法,对于其中的任意一支箭,我们都通过上面描述的方法,将这支箭的位置移动到它对应的「原本引爆的气球中最靠左的右边界位置」,那么这些原本引爆的气球仍然被引爆。右侧也已经到达了这支箭的极限。

又因为右侧边界排序过后,是有序的,我们可以每次取当前右侧边界最小的气球,把这个气球的右边界作为发射箭的位置,只要所有的左边界比我这个位置小的都可以打中(因为右边界从小到大呀!),所以直到打不中的时候,更新射箭的位置为当前的最小右边界的位置,继续扫描判断。
注意:

  • 在排序的自定义比较器中,不能直接返回i[1]-i[2];因为会有越界问题,使用if-else判断解决;

代码

class Solution {
    public int findMinArrowShots(int[][] points) {
        if(points.length == 0){
            return 0;
        }

        Arrays.sort(points, new Comparator<int[]>(){
            public int compare(int[] point1, int[] point2){
                // return point1[1] - point2[1];   // 注意这里不能这样写,会溢出
                if(point1[1] > point2[1]){
                    return 1;
                }else if(point1[1] < point2[1]){
                    return -1;
                }else{
                    return 0;
                }

            }
        });


        int pos  = points[0][1];   //  取第一个最小的右边界作为射箭的位置
        int ans = 1;
        for(int[] point: points){
            if(point[0] >  pos){   //  如果你的左边界比我的射位置靠右,射不到了,要更新射箭位置为当前最小的右边界,
                pos = point[1];
                ans += 1;
            }
        }
        return ans;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/560869.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++ 内存分区管理

一、栈区&#xff08;Stack&#xff09; 栈区用来存储函数的参数值、局部变量的值等数据。栈区是自动分配和释放的&#xff0c;函数执行时会在栈区分配空间&#xff0c;函数执行结束时会自动释放这些空间。栈区的数据是连续分配的&#xff0c;由系统自动管理。 注意事项&…

大话设计模式-依赖倒转原则

依赖倒转原则 在大话设计模式这本书中&#xff0c;作者通过电话修电脑这个例子引入了面向对象设计的基本原则之一&#xff1a;依赖倒转原则。 概念 依赖倒转原则是面向对象设计的基本原则之一&#xff0c;它用于减少类之间的耦合&#xff0c;提高系统的灵活性和可维护性。在…

明道云HAP合作伙伴计划全解析:开辟业务增长新路径

什么是明道云HAP合作伙伴计划&#xff1f; 明道云采纳的是增值伙伴商业模式。在这个模式下&#xff0c;合作伙伴通过平台型产品为终端客户提供定制应用、行业解决方案、赋能培训等增值活动&#xff0c;从而在大幅降低交付成本的同时获得多来源的收入&#xff0c;提高经营绩效水…

PLC中连接外部现场设备和CPU的桥梁——输入/输出(I/O)模块

输入&#xff08;Input&#xff09;模块和输出&#xff08;Output&#xff09;模块简称为I/O模块&#xff0c;数字量&#xff08;Digital&#xff0c;又称为开关量&#xff09;输入模块和数字量输出模块简称为DI模块和DQ模块&#xff0c;模拟量&#xff08;Analog&#xff09;输…

RK3568 android11 修改关机弹窗界面

需要修改关机弹窗界面&#xff0c;当前界面我已经按照客户需求去掉emergency 但是客户需要按其他区域可以实现返回&#xff0c;也就是点击黑色背景取消dialog 嗑代码发现黑色布局为&#xff1a; <node index"0" text"" resource-id"com.android.…

【Redis】string数据类型

文章目录 常用命令setsetnx & NXXXsetex & EXpsetex & PX msetget & mgetincr & decrincrby & decrbyincrbyfloatappendgetrangesetrangestrlen 内部编码 字符串类型是 Redis 最基础的数据类型。 在redis中所有的键都是 string 类型&#xff0c;其他的…

oracle操作系统OS认证和密码文件认证

1 说明 1.1 常见认证方式 Oracle登录认证方式主要涉及到如何验证用户身份以访问数据库。Oracle数据库提供了多种认证机制来确保数据的安全性和访问控制&#xff0c;每种方式都有其特定的使用场景和安全性考虑。以下是Oracle中常见的登录认证方式&#xff1a; 1、基于操作系统…

Vue-鼠标悬浮在缩略图图片上,弹出原图

使用Popover 弹出框实现 <template><div><el-popoverplacement"right"width"400"trigger"hover"><img src"https://fuss10.elemecdn.com/3/63/4e7f3a15429bfda99bce42a18cdd1jpeg.jpeg?imageMogr2/thumbnail/360x36…

三维天地低代码平台实现客户需求的快速交付与灵活定制

— 款合格的低代码平台应具备架构稳定、 产品质量高、 交付速度快、 运维简便的特点, 能快速实现业务需求到系统功能落地。 二十余年来, 北京三维天地科技股份有限公司一直专注于实验室信息化管理 领域, 旗下 SW- LIMS 已在化工、 环保、 食品、 科研等二十余个行业广泛应用,服…

PyTorch and Stable Diffusion on FreeBSD

Stable Diffusion在图像生成领域具有广泛的应用和显著的优势。它利用深度学习和扩散模型的原理&#xff0c;能够从随机噪声中生成高质量的图像。 官网&#xff1a;GitHub - verm/freebsd-stable-diffusion: Stable Diffusion on FreeBSD with CUDA support FreeBSD下难度主要…

docker安装并跑通QQ机器人实践(4)-bs-cqhttp搭建

go-cqhttp&#xff0c;基于 Mirai 以及 MiraiGo 的 OneBot Golang 原生实现&#xff0c;只需简单的配置, 就可以基于 go-cqhttp 使用框架开发&#xff0c;具有轻量, 原生, 高并发, 低占用, 跨平台等特点。 1 go-cqhttp 官网及可执行文件下载链接 go-cqhttp 官网&#xff1a;ht…

项目实践---贪吃蛇游戏的实现

上一章&#xff0c;我们已经分析了贪吃蛇的具体内容&#xff0c;包括它是如何实现的&#xff0c;怎样完成这个项目的&#xff0c;其中就提到了 贪吃蛇有三个代码&#xff1a;一个是测试代码&#xff0c;一个是头文件代码&#xff0c;还有一个是主函数代码。那么今天我们就来讲一…

【大数据】TiDB: A Raft-based HTAP Database

文章目录 数据库知识介绍数据库系统的ACID特性分布式系统和CAP理论关系型数据库与非关系型数据库关系型数据库非关系型数据库 OldSQL、NoSQL、NewSQLOldSQLNoSQLNewSQL OLTP、OLAP、HTAP 前言&#xff1a;为什么选择TiDB学习&#xff1f;pingCAP介绍TiDB介绍TiDB的影响力TiDB概…

什么是大语言模型以及如何构建自己的大型语言模型?

一、关于大语言模型 LLM 对于无数的应用程序非常有用&#xff0c;如果我们自己从头开始构建一个&#xff0c;那我们可以了解底层的ML技术&#xff0c;并可以根据特定需求定制LLM&#xff0c;但是对资源的需求巨大。大型语言模型是一种 ML 模型&#xff0c;可以执行各种自然语言…

《QT实用小工具·二十八》基于qt开发的各种曲线

1、概述 源码放在文章末尾 该项目实现了各种曲线的绘制&#xff0c;下面是项目的demo演示&#xff1a; 项目部分代码如下&#xff1a; #include "frmsmoothcurve.h" #include "ui_frmsmoothcurve.h" #include "smoothcurve.h" #include "…

【ThinkPHP框架教程·Part-01】ThinkPHP6.x框架安装教程

文章目录 一、框架介绍1、框架简介和版本选择2、主要新特性 二、安装步骤1、下载并运行Composer-Setup.exe2、安装TP前切换镜像3、安装稳定版4、测试运行 一、框架介绍 1、框架简介和版本选择 Thinkphp是一种基于php的开源web应用程序开发框架ThinkPHP框架&#xff0c;是免费开…

Axure设计原型图工具 Windows11安装步骤详解

文章目录 目录 文章目录 安装流程 小结 概要安装流程技术细节小结 概要 Axure 是一个流行的原型设计工具&#xff0c;它被用来创建交互式原型、线框图和用户界面设计。Axure 可以帮助用户在项目早期阶段快速制作出可交互的原型&#xff0c;以便进行用户测试、验证设计概念和与…

jetcache fastjson 泛型复杂对象JSON序列 ,反序列化

Jetcache fastjson 泛型复杂对象JSON序列 ,反序列化 默认的FastJson2 序列化存在问题增强FastJson 支持Encode 编码器Decode 解码器 默认的FastJson2 序列化存在问题 默认的序列化不能转换List 中的泛型数据类型, 从缓存拿取的list集合对象数据全部都转换成了JSONObject 增强F…

UE5 把蓝图内的变量和事件暴露给序列使用

在蓝图变量内勾选Expose to Cinematics 事件: 在角色内添加自定义事件 在序列内对着角色的号添加Event,选择Trigger 添加关键帧,然后在关键帧右键添加class,在class下绑定事件

fdisk使用的MBR分区

MBR和GPT分区 MBR分区 MBR分区一般在分区的时候 &#xff0c;MBR分区格式只能支持2TB以下的硬盘容量。 分区最多为4个主分区 或 3个主分区和1个扩展分区&#xff0c;而创建扩展分区后可以分无数个逻辑分区&#xff0c;当然跟磁盘容量有关&#xff0c; 逻辑分区在扩展分区上…