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;
}
}