> < p style = “max-width: 100%; box-sizing: border-box! Important;More article challenges

The topic of dry

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.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]Copy the code

It’s a long question, but it basically says, count the number of overlaps.

Solution: Greed

We could also do a numerator problem, where the subproblem is the contact between the intervals.

The first step is to sort the two-dimensional array by the second number.

If the two intervals coincide, the cycle continues without changing the value. The value of the current interval is compared with the minimum value of the current interval. If not, record and move the minimum value of the interval to the current current interval

Code implementation:

Execution time: 136 ms, beating 55.40% of users in all JavaScript commits

Memory consumption: 46.5 MB, beating 5.31% of all JavaScript commits

 var findMinArrowShots = function (points) {
    let length = points.length
    // The first step is still sorting, starting with the second digit of the two-dimensional array value
    points.sort(function (a, b) {
      return a[1] - b[1];
    // loop filter
    let pre = 0
    let targetnum = 1
    for (let i = 1; i < length; i++) {
      if (points[i][0] <= points[pre][1]) {
      } else{ targetnum++ pre = i; }}return targetnum
Copy the code