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&nbsp;<= xstart&nbsp;< xend&nbsp;<= 231&nbsp;- 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