Leetcode 452. minimum number of arrows to burst balloons (medium)

One 、 The main idea of the topic

label : greedy

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons

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 <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

Two 、 Their thinking

Interval overlap problem , Generally, we should think of greed （ Local optimum is equal to global optimum ）. This topic gives us a bunch of balloons of different sizes , The balloon size is represented by the range , There may be overlapping intervals , We used the fewest arrows to blow up all the balloons . We sort all the intervals according to the right boundary , Because every balloon will be broken , Therefore, we must use the first set of data obtained by sorting . As long as you shoot along the position of the rightmost boundary of the data, you will be able to break as many balloons as possible . Then move the archery position in turn , Just make statistics .

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
    
    public int findMinArrowShots(int[][] points) {
    
        //  Sorting two-dimensional arrays ？？
        Arrays.sort(points, Comparator.comparingInt(o -> o[1]));
        int res = 1;
        int end = points[0][1];
        for (int i = 1; i < points.length; i++) {
    
            if (points[i][0] <= end) {
    
                end = Math.min(end, points[i][1]);
            } else {
    
                res++;
                end = points[i][1];
            }
        }
        return res;
    }
}

Four 、 Summary notes

• 2022/7/27 Resume one question per day