1. 題目

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

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

Example: 輸入: [[10,16], [2,8], [1,6], [7,12]] 輸出: 2 解釋: 對(duì)于該樣例，我們可以在x = 6（射爆[2,8],[1,6]兩個(gè)氣球）和 x = 11（射爆另外兩個(gè)氣球）。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 按照右端點(diǎn)排序
• 第一支箭從第一個(gè)的右端點(diǎn)射出
• 找到不能相交的，再取一支箭，從不相交的那個(gè)的右端點(diǎn)射出
• 循環(huán)往復(fù)

class Solution { public:int findMinArrowShots(vector<vector<int>>& points) {if(points.empty()) return 0;sort(points.begin(), points.end(),[&](auto a, auto b){return a[1] < b[1];//按右端點(diǎn)排序});int i = 0, pos = points[0][1], count = 1;while(i < points.size()){while(i < points.size() && points[i][0] <= pos)i++;if(i < points.size())//不相交的氣球{count++;pos = points[i][1];//從其右端點(diǎn)出發(fā)}}return count;} };

1640 ms 157.4 MB

總結(jié)

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

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