有一些球形气球贴在一堵用 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 <= 105points[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：分解题目并描述解决方案
解决方案可以分为以下步骤：
- 首先对气球的直径范围按照
xend进行升序排序，这样我们可以从左到右考虑每个气球。 - 初始化弓箭数量为 1，因为至少需要一箭来引爆第一个气球。
- 遍历排序后的气球数组，对于每个气球，检查其
xstart是否大于当前箭的射出位置（即上一个气球的xend）：- 如果是，则需要射出新的箭，并将箭的数量加一。
- 如果不是，则当前箭可以继续使用，不需要增加箭的数量。
- 遍历结束后，返回弓箭的总数量。
采用贪心算法的原因是，我们每次都选择最右边的气球来射箭，这样可以尽可能多地引爆重叠的气球。
时间复杂度：O(n log n)，由于需要对数组进行排序。 空间复杂度：O(log n)，排序时使用的栈空间。
步骤3：C++ 代码实现
步骤4：讨论通过解决这个问题可以获得的启发
通过解决这个问题，我们可以学到如何使用贪心算法来优化问题的解决方案。在面对重叠区间的问题时，优先考虑覆盖范围最小的区间，这样可以减少总的操作次数。此外，我们还可以了解到排序在贪心算法中的重要作用，以及如何通过比较和选择来找到最优解。
步骤5：阐述算法在实际生活中的应用
这个算法可以在多个行业或场景中发挥作用，例如：
- 广告投放：假设广告位可以被多个广告商预订，每个广告商的预订时间段是一个区间。使用这个算法可以帮助广告平台最小化所需的广告投放次数，以覆盖所有预订时间段。
- 资源调度：在云计算中，多个任务可能需要使用相同的资源，每个任务使用资源的时间段也是一个区间。这个算法可以帮助云服务提供商最小化资源的启动次数，以服务所有任务。
具体应用示例：
假设有一个在线视频平台，用户可以在不同的时间区间预订广告。平台需要最小化广告播放次数，以覆盖所有预订的时间段。平台可以将每个预订的时间区间视为一个气球，使用上述算法来确定播放广告的最小次数。具体实现方法是，将所有预订的时间区间存储在数组中，并使用 findMinArrowShots 函数来计算所需的最小播放次数。