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

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

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

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

 

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

• 1 <= points.length <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

步骤1：定义题目的计算问题性质

题目要求找到引爆所有气球所需的最小弓箭数。这是一个典型的贪心算法问题，其中涉及到以下输入输出条件和限制：

• 输入：一个二维整数数组 points，其中 points[i] = [xstart, xend] 表示第 i 个气球的水平直径范围。
• 输出：一个整数，表示引爆所有气球所需的最小弓箭数。
• 限制：
  • 气球的数量不超过 10^5。
  • 气球的直径范围在 -2^31 到 2^31 - 1 之间。
• 边界条件：
  • 如果 points 为空，则不需要射箭，返回 0。
  • 如果 points 只有一个气球，则只需要射出一箭。

步骤2：分解题目并描述解决方案

解决方案可以分为以下步骤：

1. 首先对气球的直径范围按照 xend 进行升序排序，这样我们可以从左到右考虑每个气球。
2. 初始化弓箭数量为 1，因为至少需要一箭来引爆第一个气球。
3. 遍历排序后的气球数组，对于每个气球，检查其 xstart 是否大于当前箭的射出位置（即上一个气球的 xend）：
   • 如果是，则需要射出新的箭，并将箭的数量加一。
   • 如果不是，则当前箭可以继续使用，不需要增加箭的数量。
4. 遍历结束后，返回弓箭的总数量。

采用贪心算法的原因是，我们每次都选择最右边的气球来射箭，这样可以尽可能多地引爆重叠的气球。

时间复杂度：O(n log n)，由于需要对数组进行排序。 空间复杂度：O(log n)，排序时使用的栈空间。

步骤3：C++ 代码实现

步骤4：讨论通过解决这个问题可以获得的启发

通过解决这个问题，我们可以学到如何使用贪心算法来优化问题的解决方案。在面对重叠区间的问题时，优先考虑覆盖范围最小的区间，这样可以减少总的操作次数。此外，我们还可以了解到排序在贪心算法中的重要作用，以及如何通过比较和选择来找到最优解。

步骤5：阐述算法在实际生活中的应用

这个算法可以在多个行业或场景中发挥作用，例如：

• 广告投放：假设广告位可以被多个广告商预订，每个广告商的预订时间段是一个区间。使用这个算法可以帮助广告平台最小化所需的广告投放次数，以覆盖所有预订时间段。
• 资源调度：在云计算中，多个任务可能需要使用相同的资源，每个任务使用资源的时间段也是一个区间。这个算法可以帮助云服务提供商最小化资源的启动次数，以服务所有任务。

具体应用示例：

假设有一个在线视频平台，用户可以在不同的时间区间预订广告。平台需要最小化广告播放次数，以覆盖所有预订的时间段。平台可以将每个预订的时间区间视为一个气球，使用上述算法来确定播放广告的最小次数。具体实现方法是，将所有预订的时间区间存储在数组中，并使用 findMinArrowShots 函数来计算所需的最小播放次数。