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

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

思路

题目可以利用贪心来建模为区间交集问题，假设分别将所有相交区间取交集，得到若干个交集，我们只需要往交集处射箭即可。这样问题就转为了求这样的交集数量。

求区间交并集可以采用双指针的思路。

我们可以用排序+双指针的方法来求解区间的交集。维护这样的循环不变量：points的[p,q]区间内的点有共同的交集，其最大的交集的数值区间为[l, r]。

起初，p和q都设为0，并将l和r设置为该点的左右端点。这样循环不变量满足了初始化条件。

接下来是不变量的保持。因为我们把数组按区间左端点进行了排序，我们可以知道后面的点的左端点一定比前面的点大。这样判断是否有交集只需要判断后面点的左端点是否大于p + 1点的右端点。如果有交集，我们就尝试更新交集区间的左右端点，并尝试q + 1这个点。当没有交集时，我们就找到了所有与p + 1点有交集的点，将ans的值加一。

这样在循环结束时，我们就找到了所有点的交集个数，得到答案。

线段树？

为什么这题与区间相关，但是不用线段树呢？

首先，线段树是用来维护 区间信息 的数据结构。他能够在$O(logN)$的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

而本题需要更改区间附带的信息，因此不用线段树。

Code

class Solution {
    public int findMinArrowShots(int[][] points) {
        //直接用减法可能会溢出
        Arrays.sort(points, (int[] a, int[] b) -> Integer.compare(a[0], b[0]));
        int n = points.length;
        int ans = 0;
        //[p, q]内的点有共同交集,最大交集为[l, r]
        for (int p = 0, q = 0; p < n; q++, p = q) {
            int l = points[p][0];
            int r = points[p][1];
            while (q + 1 < n && points[q + 1][0] <= r) {
                l = points[q + 1][0];
                r = Math.min(points[q + 1][1], r);
                q++;
            }
            ans++;
        }
        return ans;
    }
}