1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> {
            if (a[1] == b[1])
                return 0;
            else if (a[1] < b[1])
                return -1;
            else
                return 1;
        });
        int currEnd = points[0][1], arrowCount = 1;
        for (int[] point : points) {
            if (point[0] > currEnd) {
                arrowCount += 1;
                currEnd = point[1];
            }
        }
        return arrowCount;
    }
}

按照end进行sort. 然后从头开始遍历. 第0个点的end作为一开始的边界, 看看之后的interval有哪些interval的start在该end之前, 直到遇到一个点不是. 此时之前的这些intervals都可以被一个arrow扎破, 遇到的这个interval需要额外的一个arrow于是让arrowCount + 1. 这种情况下, 可能之后的某个气球的start也比第0个点的end小, 但是由于它的end太大排在了后面, 比如: [1, 2], [1, 3], [3, 4], [0, 5]. 这里的[0, 5]按理说可以和[1, 2], [1, 3]一起被扎破, 但是由于它的end大排在了[3, 4]之后. 那等我们到[3, 4]的时候就发现 3是大于2的([1, 2]的end), 于是就让arrowCount + 1了. 即使有这种情况也没事儿. 因为[3, 4]无论如何需要一个单独的arrow. 后面的没赶上车的(在我们的例子中是[0, 5])只要赶上它之前的任意一个必须要有一个单独的arrow击破的interval就可以了. 在我们的例子里面, [0, 5]没赶上[1, 2]的arrow, 但是它可以赶上[3, 4]的arrow. 等于是一个interval发起一个arrow, 后续的interval看符合条件(小于发起arrow的interval的end)就一起被扎破, 不符合的话就需要自己单独开一个arrow. 如何保证后面没赶上的肯定会被include进之前某个interval发起的arrow而不是单独自己开一个? 这种情况是这个interval的start很小但是end很大, 于是它之前的某个interval自己开一个arrow了, 那么它之前开新arrow的interval必然是有个较小的end, 较大的start(至少比再之前的开arrow的interval大否则就不会新开一个arrow了)(因为只有这样才可能自己开arrow而不是赶上之前的arrow). 于是当前的没赶上的interval就能赶上前一个开arrow的interval了.

时间复杂度: O(nlogn)
空间复杂度: O(logn)