Leetcode (452) - detonate the balloon with the minimum number of arrows

Leetcode（452）—— Detonate the balloon with a minimum number of arrows

subject

There are some spherical balloons attached to a wall for XY On the wall represented by the plane . The balloons on the wall are recorded in an integer array points , among points[i] = [xstart, xend] Indicates that the horizontal diameter is xstart and xend Between the balloons . You don't know the exact of the balloon y coordinate .

A bow and arrow can follow x Axis from different points Completely vertical Shoot out . In coordinates x Shoot an arrow at , If there is a balloon with a diameter starting and ending coordinates of xstart,xend, And meet xstart ≤ x ≤ xend, Then the balloon will be tipping . The number of bows and arrows that can be shot There is no limit to . Once the bow is shot , Can move forward indefinitely .

Give you an array points , Return to what must be fired to detonate all balloons Minimum Number of bows and arrows .

Example 1：

Input ：points = [[10,16],[2,8],[1,6],[7,12]]
Output ：2
explain ： Balloons can be used 2 An arrow to blow up :

• stay x = 6 Shoot an arrow at , Break the balloon [2,8] and [1,6].
• stay x = 11 Shoot an arrow , Break the balloon [10,16] and [7,12].

Example 2：

Input ：points = [[1,2],[3,4],[5,6],[7,8]]
Output ：4
explain ： Each balloon needs to shoot an arrow , All in all 4 An arrow .

Example 3：

Input ：points = [[1,2],[2,3],[3,4],[4,5]]
Output ：2
explain ： Balloons can be used 2 An arrow to blow up :

• stay x = 2 Shoot an arrow , Break the balloon [1,2] and [2,3].
• stay x = 4 Shoot an arrow at , Break the balloon [3,4] and [4,5].

Tips :

• $1$ <= points.length <= $10^5$
• points[i].length == $2$
• $-2^{31}$ <= xstart < xend <= $2^{31-1}$

Answer key

Method 1 ： Greedy Algorithm

Ideas

​​   Sort the balloons in ascending order by the left endpoint . Then make overlapping judgment , use right Represents the right endpoint of the previous interval （ That is, the right end point of the overlapping part that can be pierced by a bow ）. If it overlaps, the right end of the overlapped part is used to refer to multiple intervals —— That is, if there is a position where a bow and arrow can explode multiple balloons, the position is used to represent these balloons .

Code implementation

I wrote it myself ：

class Solution {
    
public:
    int findMinArrowShots(vector<vector<int>>& points) {
    
        int ans = 0;    //  Total number of bows and arrows 
        //  Sort the array in ascending order by the left endpoint 
        sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b){
    return a[0] < b[0];});
        int right;    //  The right end of the previous interval 
        for(auto &it: points){
    
            //  If there is overlap, the overlapping part is used to refer to multiple intervals 
            if(ans != 0 && right >= it[0]){
    
                right = it[1] < right? it[1]: right;
            }else{
    
                ans++;
                right = it[1];
            }
        }
        return ans;
    }
};

Complexity analysis

Time complexity ：$O(n\log n)$, among $n$ It's an array $\text{points}$ The length of .sort The time complexity of the sorting function is $O(n\log n)$, The time complexity of traversing all balloons and calculating the answer is $O(n)$, It is smaller than the former in the progressive sense , So we can ignore .
Spatial complexity ：$O(\log n)$, This is the stack space needed for sorting .