452. 用最少数量的箭引爆气球（难度：中等）

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

解题思路

先将所有气球的坐标排序;
标记上一次炸裂的气球的尾端，如果其他气球的最前端在尾端之前，则会被同一只箭射中；

否则为另一只箭；

题解

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;

    
    Arrays.sort(points, Comparator.comparingInt(o -> o[1]));

    int minNumsOfArrows = 1;
    int prevBurst = points[0][1];
    for (int index = 1, pointsLength = points.length; index < pointsLength; index++) {
        if (points[index][0] > prevBurst) {
            ++minNumsOfArrows;
            prevBurst = points[index][1];
        }
    }
    return minNumsOfArrows;
}
复制代码

测试

MinNumOfArrowsToBurstBalloons minNumOfArrowsToBurstBalloons = new MinNumOfArrowsToBurstBalloons();

@Test
public void test_case1() {
    int[][] points = new int[][]{
            {10, 16},
            {2, 8},
            {1, 6},
            {7, 12}
    };
    Assertions.assertEquals(2, minNumOfArrowsToBurstBalloons.findMinArrowShots(points));
}

@Test
public void test_case2() {
    int[][] points = new int[][]{
            {1, 2},
            {3, 4},
            {5, 6},
            {7, 8}
    };
    Assertions.assertEquals(4, minNumOfArrowsToBurstBalloons.findMinArrowShots(points));
}

@Test
public void test_case3() {
    int[][] points = new int[][]{
            {1, 2},
            {2, 3},
            {3, 4},
            {4, 5}
    };
    Assertions.assertEquals(2, minNumOfArrowsToBurstBalloons.findMinArrowShots(points));
}

@Test
public void test_case4() {
    int[][] points = new int[][]{
            {1, 2},
    };
    Assertions.assertEquals(1, minNumOfArrowsToBurstBalloons.findMinArrowShots(points));
}

@Test
public void test_case5() {
    int[][] points = new int[][]{
            {2, 3},
            {2, 3}
    };
    Assertions.assertEquals(1, minNumOfArrowsToBurstBalloons.findMinArrowShots(points));
}

@Test
public void test_case6() {
    int[][] points = new int[][]{
            {3, 9},
            {7, 12},
            {3, 8},
            {6, 8},
            {9, 10},
            {2, 9},
            {0, 9},
            {3, 9},
            {0, 6},
            {2, 8}
    };
    Assertions.assertEquals(2, minNumOfArrowsToBurstBalloons.findMinArrowShots(points));
}
复制代码