在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結束坐標。由于它是水平的，所以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（射爆另外兩個氣球）。

貪心規律如下：
1.對于某個氣球，至少需要使用1只弓箭將它擊穿。
2.在這只氣球將其擊穿的同時，盡可能擊穿其他更多的氣球

算法思路：

1. 對各個氣球進行排序，按照氣球的左端點從小到大排序。
2. 遍歷氣球數組，同時維護一個射擊區間，在滿足可以將當前氣球射穿的情況下，盡可能擊穿更多的氣球，每擊穿一個新的氣球，更新一次射 擊區間(保證射擊區間可以將新氣球也擊穿)。
3. 如果新的氣球沒辦法被擊穿了，則需要增加一名弓箭手，即維護一個新 的射擊區間(將該氣球擊穿)，隨后繼續遍歷氣球數組

實現如下:

int findMinArrowShots(vector<vector<int>>& points) {if (points.size() == 0) {return 0;}sort(points.begin(),points.end(),cmp);int num = 1;int shoot_begin = points[0][0];int shoot_end = points[0][1];for (int i = 1; i < points.size(); ++i) {//隨著氣球數量的遞增，區間不斷縮小if(shoot_end >= points[i][0]) {shoot_begin = points[i][0];if (shoot_end > points[i][1]) {shoot_end = points[i][1];}} else {//當發現區間的end 小于氣球的起始邊界，則重新劃分區間，箭的數量增加num ++;shoot_begin = points[i][0];shoot_end = points[i][1];}}return num;
}

總結

以上是生活随笔為你收集整理的leetcode-452 用最少数量的箭引爆气球的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。