在二維空間中有許多球形的氣球。對(duì)于每個(gè)氣球，提供的輸入是水平方向上，氣球直徑的開(kāi)始和結(jié)束坐標(biāo)。由于它是水平的，所以縱坐標(biāo)并不重要，因此只要知道開(kāi)始和結(jié)束的橫坐標(biāo)就足夠了。開(kāi)始坐標(biāo)總是小于結(jié)束坐標(biāo)。

一支弓箭可以沿著 x 軸從不同點(diǎn)完全垂直地射出。在坐標(biāo) x 處射出一支箭，若有一個(gè)氣球的直徑的開(kāi)始和結(jié)束坐標(biāo)為 xstart，xend， 且滿足 xstart ≤ x ≤ xend，則該氣球會(huì)被引爆。可以射出的弓箭的數(shù)量沒(méi)有限制。 弓箭一旦被射出之后，可以無(wú)限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。

給你一個(gè)數(shù)組 points ，其中 points [i] = [xstart,xend] ，返回引爆所有氣球所必須射出的最小弓箭數(shù)。

示例 1：

輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：對(duì)于該樣例，x = 6 可以射爆 [2,8],[1,6] 兩個(gè)氣球，以及 x = 11 射爆另外兩個(gè)氣球

代碼

class Solution {public int findMinArrowShots(int[][] points) {if(points.length==0) return 0;Arrays.sort(points, new Comparator<int[]>() {//按區(qū)間末尾的大小，從小到大排序@Overridepublic int compare(int[] o1, int[] o2) {return o1[1]>o2[1]?1:-1;}});int res=1,preEnd=points[0][1];for(int i=0;i<points.length;i++){if(points[i][0]>preEnd)//如果當(dāng)前氣球的區(qū)間起始，不在前一個(gè)區(qū)間末尾，就需要另外一顆子彈{res++;preEnd=points[i][1];}}return res;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 452. 用最少数量的箭引爆气球（贪心算法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。