452.用最少数量的箭引爆气球

题目描述

题解

贪心算法

与435题无重叠区间一样, 都是先根据每个区间的结束端进行排序, 一共有多少无重叠区域, 那就需要多少支箭.

不过不同点在于, 这道题目中说只要接触到就能引爆, 所以要修改一下边界条件

public int findMinArrowShots(int[][] points) {
    if (points.length == 0)
        return 0;
    Arrays.sort(points, (int[] a, int[] b) -> {
        return a[1] - b[1];
    });

    int count = 1;
    int x_end = points[0][1];
    for (int[] interval : points) {
        int start = interval[0];
        if (start > x_end) {
            count++;
            x_end = interval[1];
        }
    }
    return count;
}