一、題目452. 用最少數(shù)量的箭引爆氣球

LeetCode地址：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
難度：中等
在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結(jié)束坐標。由于它是水平的，所以縱坐標并不重要，因此只要知道開始和結(jié)束的橫坐標就足夠了。開始坐標總是小于結(jié)束坐標。

一支弓箭可以沿著 x 軸從不同點完全垂直地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結(jié)束坐標為 x_start，x_end，且滿足 x_start <= x <= x_end，則該氣球會被引爆?？梢陨涑龅墓臄?shù)量沒有限制。 弓箭一旦被射出之后，可以無限地前進。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。

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

示例 1：

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

示例 2：

輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4

示例 3：

輸入：points = [[1,2],[2,3],[3,4],[4,5]]
輸出：2

提示：

0 <= points.length <= 10⁴
points[i].length == 2
-2³¹ <= x_start < x_end <= 2³¹ - 1

二、解題思路

與其他區(qū)間類問題的解題思路一樣都是貪心思想, 先排序, 然后遍歷檢查是否滿足合并區(qū)間的條件
ps:算法入門-435. 無重疊區(qū)間 - 簡書 (jianshu.com)

三、實現(xiàn)過程

c++方法一

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        // 對于empty
        if (points.empty()){
            return 0;
        }  
        // 按照區(qū)間開始位置排序
        sort(points.begin(), points.end(),
            [](const vector<int> &a, const vector<int> b) {
                return a[0] < b[0];
            });

        int count = 1;
        int len = points.size();
        // 右邊區(qū)間初始化;
        int right = points[0][1];
        for (int i = 1; i < len; i++) {
            //如果下一個區(qū)間左端超過當前右區(qū)間，換下一個箭
            if(points[i][0] > right){
                count++;
                right = points[i][1];
            }else{
                if(points[i][1] < right){
                    right = points[i][1];
                }
            }
        }
        return count;
    }
};

c++方法二(官方題解)

鏈接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/solution/yong-zui-shao-shu-liang-de-jian-yin-bao-qi-qiu-1-2/

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        // 對于empty
        if (points.empty()) {
            return 0;
        }
        sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[1] < v[1];
        });
        int pos = points[0][1];
        int ans = 1;
        for (const vector<int>& balloon: points) {
            if (balloon[0] > pos) {
                pos = balloon[1];
                ++ans;
            }
        }
        return ans;
    }
};

PHP

class Solution {

    /**
     * @param Integer[][] $points
     * @return Integer
     */
    function findMinArrowShots($points) {
        if( count($points) == 0 ){
            return 0;
        }
        
        usort($points,function($value1,$value2){
            if( $value1[0] > $value2[0] ){
                return 1;
            }else if( $value1[0] < $value2[0] ){
                return -1;
            }else{
                if( $value1[1] > $value2[1] ){
                    return 1;
                }else if($value1[1] < $value2[1]){
                    return -1;
                }else{
                    return 0;
                }
            }
        });
        
        $right = $points[0][1];
        $count = 1;
        $len = count($points);
        for($i = 1;$i < $len;$i++){
            if($points[$i][0] > $right){
                $count++;
                $right = $points[$i][1];
            }else{
                if($points[$i][1] < $right){
                    $right = $points[$i][1];
                }
            }
        }
        
        return $count;
    }
}

JavaScript

/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function(points) {
    if(points.length == 0){
        return 0;
    }
    points.sort((a, b) => a[0] - b[0])
    //console.log(points)
    
    // 射擊次數(shù)
    var count = 1;
    // 維護射擊區(qū)間的右邊界
    var right = points[0][1];
    for (var i = 1; i < points.length; i++) {
        if (points[i][0] > right) { // 新的氣球左端點大于射擊區(qū)間右邊界，更新射擊區(qū)間右邊界
            count++;
            right = points[i][1];
        } else { // 新的氣球左端點小于等于射擊區(qū)間的右邊界
            if (points[i][1] < right) { // 如果右端點也比射擊區(qū)間右邊界小
                right = points[i][1];
            }
        }
    }
    
    return count;
    
};

四、小結(jié)

這類區(qū)間問題處理思路基本上就是排序 + 貪心，選擇哪種排序思路，對后續(xù)操作影響是非常大的。在c++方法二中對區(qū)間右端排序處理起來要比方法一快許多，似乎這類問題選擇區(qū)間右端排序要快上許多。

c++兩種方法比較