0452. Minimum Number of Arrows to Burst Balloons ================================================ 题目信息 -------- :题号: 0452 :难度: Medium :主题: 水平区间、垂直箭、闭区间命中、最少箭数 :原题: `LeetCode 0452 `_ :重点: 气球横向范围是闭区间、箭的横坐标命中范围即可、同一箭可击破多个区间、端点命中有效 题目重述 -------- 每个气球在水平轴上的直径范围由闭区间 ``[xstart, xend]`` 表示。可以从任意横坐标 ``x`` 垂直射出一支箭;当 ``xstart <= x <= xend`` 时,该箭会击破该气球。箭可无限向上飞行,因此同一支箭能够击破所有包含该横坐标的气球。 给定全部气球区间 ``points``,返回击破所有气球所需的最少箭数。``points.length`` 位于 ``[1, 10^5]``,每个区间满足 ``xstart < xend``,端点在 32 位有符号整数范围内。 自建示例 -------- 端点处的一支箭命中两个气球: .. code-block:: text 输入:points = [[1,4], [2,3], [5,7], [7,9]] 输出:2 解释:在 x = 2 或 3 射一箭可击破前两个气球;在 x = 7 射一箭可同时击破后两个闭区间。 所有区间互不相交: .. code-block:: text 输入:points = [[0,1], [2,3], [4,5]] 输出:3 解释:不存在一个横坐标同时落入两个区间,因此每个气球都需要单独一箭。 按右端点贪心固定下一支箭 ------------------------ 将区间按右端点从小到大排序。处理当前区间时,如果它的左端点仍不大于上一支箭的位置,说明闭区间包含该箭,无需增加箭;若左端点已经大于箭的位置,当前区间与此前箭无法共同覆盖,必须在它的右端点重新射箭。 把新箭放在当前区间的最右端,能覆盖当前区间,并为后续区间留下最大的共同交集。每次新增箭都由当前最早结束、尚未被覆盖的区间强制产生,因此不会比其他选择使用更少的箭。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int findMinArrowShots(std::vector>& points) { std::sort(points.begin(), points.end(), [](const auto& left, const auto& right) { return left[1] < right[1]; }); int arrows = 0; long long arrow = LLONG_MIN; for (const auto& interval : points) { if (arrows == 0 || interval[0] > arrow) { ++arrows; arrow = interval[1]; } } return arrows; } }; 代码分析 -------- 闭区间端点有效,所以 ``interval[0] == arrow`` 时当前气球已经被命中,不能错误地再加一支箭。选择当前区间右端点作为箭位保持了对未来区间的最大兼容范围;排序耗时 ``O(n log n)``,扫描为 ``O(n)``,额外空间取决于排序实现,算法本身为 ``O(1)``。