Leetcode notes 452. minimum number of arrows to burst balloons (medium) 452. detonate balloons with the minimum number of arrows (medium)

1. Title Description ：

         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 the minimum number of bows and arrows that must be fired to detonate all balloons .

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].

2. Code ：

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty()){
            return 0;
        }
		
		// Why not use two #if 0  Replace #if 1 The content in  , Logically speaking, it's not faster ？
		#if 1
        sort(points.begin(), points.end(), [](const vector<int> &a, const vector<int> &b){
            return a[1] < b[1];
        });
		#endif
		#if 0
		sort(points.begin(), points.end(), cmp);
		#endif
        int count = 1;
        int prev = points[0][1];
        for(int i = 1; i < points.size(); ++i){
            if(points[i][0] > prev){
                ++count;
                prev = points[i][1];
            }
        }
        return count; 
    }
	#if 0
	static bool cmp(const vector<int> &a, const vector<int> &b){
		return a[1] < b[1];
	}
	#endif
};

3. Their thinking ：

        Since we need to use the least arrows to break through all balloons , Then each arrow should break through the balloon as much as possible （ The local optimum constitutes the global optimum ）, In this way, the number of arrows used at last must be the least .

Through this picture , When the arrow moves left and right , Only this position can pass through four balloons or more , Achieve local optimal effect , This position depends on the balloon with the smallest right boundary . therefore , Just arrange the balloons in ascending order on the right boundary , After determining the position of the first arrow （ The right boundary of the first balloon , Suppose the coordinates are x1）, You can make other right boundaries larger than x1, The left boundary is less than x1 All the balloons go through , Repeat the operation for the remaining balloons .

4. Code section

@. about sort Pass in the parameter , I wrote two ：

         The first is #if 1 The key to the content in is that the third parameter is anonymous function , The format of anonymous function is ：[ External variable access method specifier ]( Parameter table ) -> Return value { Statement of body }. There are two kinds of specifiers ： The first one is = It is not allowed to change the value of variables defined outside the statement ; The second kind  & It is allowed to change the value of variables defined outside the statement .

        The second is two #if 0 The content in , The custom function must be static Type of , because sort() Function requires parameters to be static , Personally, I think this way should run faster , I also read some other people's blogs and said the same , But in leetcode The first way is to run faster , nearly 100ms The leading , Hope to see this friend answer .