Open nobodyto opened 2 years ago
链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons 题目要求： 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例 1： 输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球 示例 2： 输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 示例 3： 输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 示例 4： 输入：points = [[1,2]] 输出：1 示例 5： 输入：points = [[2,3],[2,3]] 输出：1 提示： 1 <= points.length <= 104 points[i].length == 2 -231 <= xstart < xend <= 231 - 1
分析：
如图，假设有4个气球需要被引爆。现沿垂直X轴方向随机的发射一支箭，如图1中红色实线箭头。图1中随机发射的一支箭仅仅引爆了一个气球，显然，它可以做的更好。我们将图1中射出的箭如果像右移动，可以让它引爆更多的气球。移动到图2所示的位置时，此时箭正好能引爆3个气球，如果继续向右移动，则此箭能引爆的气球数将减少，同时，最左侧的气球将需要新发射一支箭去引爆。
可以将射气球游戏，抽象成数学问题：在X轴上有多个区间（气球的起始点看做一个区间），期望找到最少的点（一支箭的发射位置），使得每个区间至少包含一个点。
根据上面移箭方式，结合抽象模型，我们不难得到如下发现： 1.向右移箭时，一支箭的最合适的发射点，可以认为在某个区间的右边界点上； 2.此右边界点是，此箭能引爆的所有气球，右边界点中最靠左的；
根据如上发现，我们可以思考出初步的解题思路： 1.为了准确快速判断，箭的发射点，我们需要对区间的右边界点进行从小到大进行排序； 2.对所有区间进行遍历，依次进行判断，如果： 1)此区间左边界点在上一个区间右边界点的左侧，则认为起可以跟上一个区间一起被同一支箭引爆； 2)此区间左边界点在上一区间右边界点的右侧，则认为需要新引一支箭；
写出java代码如下： class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) { return 0; } Arrays.sort(points, new Comparator<int[]>() { public int compare(int[] point1, int[] point2) { if (point1[1] > point2[1]) { return 1; } else if (point1[1] < point2[1]) { return -1; } else { return 0; } } }); int pos = points[0][1]; int ans = 1; for (int[] balloon: points) { if (balloon[0] > pos) { pos = balloon[1]; ++ans; } } return ans; } }
复杂度分析 时间复杂度： O(nlogn)，其中n是数组points 的长度。排序的时间复杂度为 O(nlogn)，对所有气球进行遍历并计算答案的时间复杂度为 O(n)，其在渐进意义下小于前者，因此可以忽略。
空间复杂度： O(logn)，即为排序需要使用的栈空间。
特哥牛！
renchord
commented
2 years ago
链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons 题目要求： 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
示例 1： 输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球 示例 2： 输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 示例 3： 输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 示例 4： 输入：points = [[1,2]] 输出：1 示例 5： 输入：points = [[2,3],[2,3]] 输出：1 提示： 1 <= points.length <= 104 points[i].length == 2 -231 <= xstart < xend <= 231 - 1
分析：
如图，假设有4个气球需要被引爆。现沿垂直X轴方向随机的发射一支箭，如图1中红色实线箭头。图1中随机发射的一支箭仅仅引爆了一个气球，显然，它可以做的更好。我们将图1中射出的箭如果像右移动，可以让它引爆更多的气球。移动到图2所示的位置时，此时箭正好能引爆3个气球，如果继续向右移动，则此箭能引爆的气球数将减少，同时，最左侧的气球将需要新发射一支箭去引爆。
可以将射气球游戏，抽象成数学问题：在X轴上有多个区间（气球的起始点看做一个区间），期望找到最少的点（一支箭的发射位置），使得每个区间至少包含一个点。
根据上面移箭方式，结合抽象模型，我们不难得到如下发现： 1.向右移箭时，一支箭的最合适的发射点，可以认为在某个区间的右边界点上； 2.此右边界点是，此箭能引爆的所有气球，右边界点中最靠左的；
根据如上发现，我们可以思考出初步的解题思路： 1.为了准确快速判断，箭的发射点，我们需要对区间的右边界点进行从小到大进行排序； 2.对所有区间进行遍历，依次进行判断，如果： 1)此区间左边界点在上一个区间右边界点的左侧，则认为起可以跟上一个区间一起被同一支箭引爆； 2)此区间左边界点在上一区间右边界点的右侧，则认为需要新引一支箭；
写出java代码如下： class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) { return 0; } Arrays.sort(points, new Comparator<int[]>() { public int compare(int[] point1, int[] point2) { if (point1[1] > point2[1]) { return 1; } else if (point1[1] < point2[1]) { return -1; } else { return 0; } } }); int pos = points[0][1]; int ans = 1; for (int[] balloon: points) { if (balloon[0] > pos) { pos = balloon[1]; ++ans; } } return ans; } }
复杂度分析 时间复杂度： O(nlogn)，其中n是数组points 的长度。排序的时间复杂度为 O(nlogn)，对所有气球进行遍历并计算答案的时间复杂度为 O(n)，其在渐进意义下小于前者，因此可以忽略。
空间复杂度： O(logn)，即为排序需要使用的栈空间。