[greedy algorithm Part 4] interval problem: detonate the balloon with the least number of arrows

452. Detonate the balloon with a minimum number of arrows

There are many spherical balloons in two-dimensional space. For each balloon, the input provided is the start and end coordinates of the balloon diameter in the horizontal direction.

Because it is horizontal, the ordinate is not important, so it is enough to know the abscissa of the beginning and end. 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 the coordinate X. if the start and end coordinates of the diameter of a balloon are xstart, xend and xstart ≤ x ≤ xend, the balloon will be detonated.

There is no limit to the number of bows and arrows you can shoot. Once a bow and arrow is shot, it can move forward indefinitely. We want to find the minimum number of bows and arrows needed to detonate all balloons.

Give you an array of points, where points [i] = [xstart,xend] returns 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]]

Is to find the intersection of ranges

Output: 2
Explanation: for this example, x = 6 can explode [2,8], [1,6] two balloons, and x = 11 can explode the other two balloons

Example 2:
[1,4], [3,4], [4,5], [4,5]
Output: 4

Example 3:
Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2

Example 4:
Input: points = [[1,2]]
Output: 1

Example 5:
Input: points = [[2,3],[2,3]]
Output: 1

Local optimization: when the balloons overlap and shoot together, the bows and arrows used are the least.
Global Optimization: blast all balloons with the least bow and arrow.
Core: find the intersection of scope

Solution 1: sort the left boundary in ascending order and cover it from left to right

class Solution {
    public int findMinArrowShots(int[][] points) {
      if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] > o2[0] ? 1: -1;  // Ascending order
            }
        });
      int arrow=1;
      for (int i=1;i<points.length;i++){  // From [1, length-1], only i-1 and i can appear, and i+1 cannot appear
          if (points[i-1][1] < points[i][0])
              arrow++;
          else{  // Less than or equal to points [I-1] [1] > = points [i] [0]
              // After changing the element i + +, point[i][1] is the points[i-1][1] compared above
              points[i][1] = Math.min(points[i-1][1],points[i][1]);
          }
      }
      return arrow;
    }
}

In java, int a = -2147483646 - 2147483646 = 4, which will not be negative, so the minus sign return o1[0]-o2[0] cannot be used;
Can only use > < = = return O1 [0] > O2 [0]? 1: -1;

Solution 2: the left boundary is sorted in ascending order, covering from right to left

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] > o2[0] ? 1: -1;  // Ascending order
            }
        });
        int arrow=1;
        for (int i=points.length-2;i>=0;i--){  // From [1, length-1], only i-1 and i can appear, and i+1 cannot appear
            if (points[i][1] < points[i+1][0])
                arrow++;
            else{ 
                points[i][0] = Math.max(points[i][0],points[i+1][0]);
            }
        }
        return arrow;
    }
}

Solution 3: the right boundary is sorted in descending order, covering from right to left

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] < o2[1] ? 1: -1;  // Right boundary descending sort
            }
        });
        int arrow=1;
        for (int i=1;i<points.length;i++){  // From [1, length-1], only i-1 and i can appear, and i+1 cannot appear
            if (points[i-1][0] > points[i][1])  // The left boundary of i-1 is larger
                arrow++;
            else{  // Less than or equal to points [I-1] [1] > = points [i] [0]
                // After changing the element i + +, point[i][1] is the points[i-1][1] compared above
                points[i][0] = Math.max(points[i-1][0],points[i][0]);
            }
        }
        return arrow;
    }
}

Solution 4: sort the right boundary in descending order and cover it from left to right (reverse it twice, and it's the same from "solution 1")

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] < o2[1] ? 1: -1;  // Descending arrangement of right boundary
            }
        });
        int arrow=1;
        for (int i=points.length-2;i>=0;i--){  // From [1, length-1], only i-1 and i can appear, and i+1 cannot appear
            if (points[i+1][1] < points[i][0])
                arrow++;
            else{  // Less than or equal to points [I-1] [1] > = points [i] [0]
                // After changing the element i + +, point[i][1] is the points[i-1][1] compared above
                points[i][1] = Math.min(points[i][1],points[i+1][1]);
            }
        }
        return arrow;
    }
}

Non overlapping interval

Divide letter interval

Merge interval

Added by AnsonM on Fri, 18 Feb 2022 12:00:19 +0200