Leetcode 452. 用最少数量的箭引爆气球_达达达达锅的博客-程序员秘密

技术标签: Leetcode  LeetCode  

在二维空间中有许多球形的气球。对于每个气球,提供的输入是水平方向上,气球直径的开始和结束坐标。由于它是水平的,所以y坐标并不重要,因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

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

Example:

输入:
[[10,16], [2,8], [1,6], [7,12]]

输出:
2

解释:
对于该样例,我们可以在x = 6(射爆[2,8],[1,6]两个气球)和 x = 11(射爆另外两个气球)。

基本思路:这道题完全和https://leetcode-cn.com/problems/merge-intervals/description/ 合并区间相反,合并区间是将所有相交的区间合并,这个题的基本解法是将所有不想交的区间全部找出来即可。贪心算法……

 

class Solution {
public:
    static bool com(pair<int, int>& A,pair<int, int>& B){
		return A.first<B.first;
    }
    
    int findMinArrowShots(vector<pair<int, int>>& points) {
        if(points.size()==0) return 0;
        sort(points.begin(),points.end(),com);
		int End=points[0].second,Res=0;
		for(int i=0;i<points.size();i++){
			if(points[i].first>End){
				Res++;	
                End=points[i].second;
			}
            else{
                End=min(points[i].second,End);
            }
            
		}
		return Res==-1?Res=1:++Res;
    }
};

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/liaoxuda_edu/article/details/82845560

智能推荐

Linux中的 进程概念、进程创建 和 GDB多进程调试 [Linux高并发服务器开发]_thread_pid_Monkey Ji的博客-程序员秘密

进程是正在运行的程序的实例,是一个具有一定独立功能的程序关于某个数据结合的一次运行活动。它是操作系统动态执行的基本单元,在传统的操作系统中,进程既是基本的分配单元,也是基本的执行单元。

串行器说明书_max96717_Yixingtianxia276的博客-程序员秘密

Click herefor production status of specific part numbers.MAX96717F CSI-2 to GMSL2 SerializerGeneral Description Benefits and Features The MAX96717F converts MIPI CSI-2 or LVCMOS paral- lel video to a single link GMSL2 while sending and receiv.

matlab变量区表示函数,MATLAB中的工作区,变量和函数_weixin_39594895的博客-程序员秘密

本文概述工作空间工作区包含我们在MATLAB中工作时创建的所有变量。每当我们为变量分配值时, 它都会自动在工作空间中获取空间。关闭环境后, 工作空间变量将消失, 因此请将这些变量保存在文件中以备后用。我们可以将变量从数据文件导入MATLAB。我们也可以从其他程序将变量导入MATLAB。赋值运算符(=)有助于创建变量。要从工作空间访问变量, 我们需要在命令行中输入其名称。要查看工作空间中所有可用的变...

Android 局域网扫描_weixin_30466953的博客-程序员秘密

本篇简单介绍通过UDP广播扫描局域网设备IP,并且通过ZMQ进行通信。UDP连接主要流程:1.1 Step1:主机发送广播信息,并指定接收端的端口(9000) 广播地址(255.255.255.255)2.2 Step2:主机将数据报以固定报头并且和用户数据一起打包封装在DatagramPacket,为了防丢失一共发三次,每次发送以后监听一段时间3.3 Step3:接收端监听端口(900...

深度完美 XP SP3 完美优化装机版 V2013    _weixin_33863087的博客-程序员秘密

深度完美 XP SP3 完美优化装机版 V2013 文件名: DEEPBBS_GHOSTXPSP3_v2013.iso 大小: 863.63 MB MD5: 69cebb583b5f44aac88823687efff347 SHA1: 6fecf393253eadd61af4089bd56a5ba6d5303a93 下载地址 http://zc0755.cn一、主...

pip常用命令_pip命令的使用方法_赶路人儿的博客-程序员秘密

pip类似RedHat里面的yum,安装Python包非常方便。本节详细介绍pip的安装、以及使用方法。1、pip安装包# pip install SomePackage [...] Successfully installed SomePackage2、pip查看已安装的包# pip show --files SomePackage Name: SomeP

随便推点

一次mysql数据库迁移的过程记录_yumushui的博客-程序员秘密

附件中是昨天进行当铺网MySQL数据库迁移的步骤,也适合其他业务MySQL数据库的迁移,可以参考。对于该迁移步骤有几点需要说明:    1.该迁移方法有几个必须满足的前提条件:原服务器和新服务器都有安装好并且正常可用的 MySQL 和 Percona Xtrabackup 软件环境;网络可以连通,或者可以进行文件传输;    2.实际迁移切换时,需要考虑一下原数据库的状态,或者

R语言中round()函数的使用_r round_meizi2222的博客-程序员秘密

round(timeDate)round()所属R语言包:timeDate                                        Rounding and Truncating 'timeDate' Objects                                         四舍五入和截断TIMEDATE对象的        

openstack FWaaS 防火墙项目因缺少维护者被弃用_xin053的博客-程序员秘密

介绍熟悉防火墙的都知道,防火墙一般放在网关上,用来隔离子网之间的访问。因此,防火墙即服务(FireWall as a Service)也是在网络节点上(具体说来是在路由器命名空间中)来实现。目前,OpenStack 中实现防火墙还是基于 Linux 系统自带的 iptables,所以大家对于其性能和功能就不要抱太大的期望了。一个可能混淆的概念是安全组(Security Group),安全组的对象是虚拟网卡,由L2 Agent来实现,比如neutron_openvswitch_agent 和 neutr

Java向上转型与向下转型 (一)_Ryuka-fly的博客-程序员秘密

我们在Java编程中经常碰到类型转换,对象类型转换主要包括向上转型和向下转型。5.13.1 向上转型我们在现实中常常这样说:这个人会唱歌。在这里,我们并不关心这个人是黑人还是白人,是成人还是小孩,也就是说我们更倾向于使用抽象概念“人”。再例如,麻雀是鸟类的一种(鸟类的子类),而鸟类则是动物中的一种(动物的子类)。我们现实中也经常这样说:麻雀是鸟。这两种说法实际上就是所谓的向上转型,通俗

Proguard用法_zhangjunli的博客-程序员秘密

混淆(Proguard)用法最近项目中遇到一些混淆相关的问题,由于之前对proguard了解不多,所以每次都是面向Stackoverflow的编程。copy别人的答案内心还可以接受,但是copy了之后不懂别人的逻辑是无法忍受的。首先不清楚别人的答案是不是一定符合自己的需求;其次,再遇到同类问题还是得抓瞎。于是下决心看了一下proguard的官方文档。很长,但是很详细,在这里整理一下笔记,分享给...

利用七牛云SDK实现文件的简单上传和下载_qiniu-y-sdk_M__Y的博客-程序员秘密

首先要添加七牛云的依赖:代码如下:import com.google.gson.Gson;import com.qiniu.common.QiniuException;import com.qiniu.http.Response;import com.qiniu.storage.Configuration;import com.qiniu.storage.Region;import com.qiniu.storage.UploadManager;import com.qiniu..

推荐文章

热门文章

相关标签