2022.01.03 - SX09-17.用最少数量的箭引爆气球

• 1. 题目
• 2. 思路
• • (1) 贪心算法
• 3. 代码

• 从左往右扫描所有气球，当确定要用一支新箭射爆某个气球时，为了使该箭能够同时射爆更多气球，应该在原气球的最右端或最左端射出该箭。
• 为了满足上面的贪心策略，需要将所有气球按照右端点的值进行排序，这样可以保证当一个气球的左端点小于前一个气球的右端点时，其右端点不会小于前一个气球的右端点。
• 从左往右遍历气球，当气球的左端点大于前一个气球的右端点时，则需要增加一支箭。
• 注意！排序时应该调用Integer.compare()，而不能直接相减，可能会溢出。

import java.util.Arrays;
import java.util.Comparator;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, new Comparator() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });
        int res = 1;
        int right = points[0][1];
        for (int[] point : points) {
            if (point[0] > right) {
                res++;
                right = point[1];
            }
        }
        return res;
    }
}