Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

Detonate the balloon with the minimum number of arrows

Subject address: leetcode-cn.com/problems/mi…

Title description:

There are many spherical balloons in two dimensions. For each balloon, the input provided is the start and end coordinates of the balloon diameter in the horizontal direction. Since it’s horizontal, the y-coordinate doesn’t matter, so it’s enough to know where the x-coordinate starts and ends. The start coordinate is always less than the end coordinate.

A bow and arrow can be shot completely vertically from different points along the X-axis. Shoot an arrow at coordinate X. If there is a balloon whose diameter starts and ends at coordinates xstart, xend, and xstart ≤ x ≤ xend, the balloon will be detonated. There is no limit to the number of bows and arrows that can be fired. Once a bow is fired, it can go indefinitely. We want to find the minimum number of arrows needed to detonate all the balloons.

Give you an array of points, where points [I] = [xstart,xend] returns the minimum number of arrows that must be fired to detonate all the balloons.

The sample

Input: points = [[10.16], [2.8], [1.6], [7.12]] output:2Explanation: For this example, x =6Can explode [2.8], [1.6] two balloons and x is equal to11Shoot the other two balloonsCopy the code
Input: points = [[1.2], [3.4], [5.6], [7.8]] output:4
Copy the code
Input: points = [[1.2], [2.3], [3.4], [4.5]] output:2
Copy the code

Subject analysis

The difficulty of this question is not high, after seeing the topic and example, finally draw a picture of their own, so that it can be more intuitive to see.

In the example of [[10,16],[2,8],[1,6],[7,12]], the position of the balloon is roughly these horizontal lines, and the arrow is the position from which the bow is fired, which can be toggled continuously.

But if every range is constantly tested to shoot arrows and detonate balloons, the numbers are huge. So here we need to find the extreme value, reorder the array of balloons according to the right boundary from the largest to the smallest, and then shoot the arrow with the right boundary of the first balloon as the coordinate (must explode at least one balloon). Then the array of balloons traversal, the coordinates can detonate the balloon from the array excluded, and then the current array of the first balloon on the right edge of the arrow again, so repeat the loop to the array no balloons.

code

Loop with while, if the current array length is less than or equal to 0, end loop, each shot position is the right edge of the first value of the current array, and the number of shots +1. The array is filtered by filter, and the new array composed of existing balloons overwrites the current balloon array.

var findMinArrowShots = function(points) {
    // Sort the array by the rightmost boundary
    points.sort((a, b) = >{
        return a[1] - b[1];
    })
    let attackCount = 0, attackPos = -1;
    while(points.length > 0) {
        // Archery position
        attackPos = points[0] [1];
        attackCount++;
        points = points.filter((item) = >{
            if(attackPos >= item[0] && attackPos <= item[1]) {
                return false;
            } else {
                return true}})}return attackCount;
};
Copy the code