452. 用最少数量的箭引爆气球(稍微总结一下贪心)

本文主要是介绍452. 用最少数量的箭引爆气球(稍微总结一下贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心思想：完成目标的前提下，尽可能找到最优的边界。一般题目的表述是：要完成目标，最少需要...

45 跳跃题目，就是先确定能跳的区间之后再找到能跳的最大数。

本题目气球，先排序，然后确定能射爆该气球的前提下尽可能多的去射爆其他气球。

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

难度中等343

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 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

 

提示：

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

思路：首先两区间相交的条件是某一区间的一个端点正好落在另一区间之间。 

按右端点排序，这样做的目的是保证下一个区间的右端点会大于等于前一个区间右端点，那么我们只要判断当前区间左边端点是否落在前一个区间右端点之前即可。

排序后从左至右遍历数组，给第一个区间一支箭从最右边射出去就刚好保证了在射爆当前气球（选择当前区间）的情况下尽可能多射爆其他气球（多相交其他区间）。

        解答成功:
            执行耗时:19 ms,击败了86.51% 的Java用户
            内存消耗:46.4 MB,击败了5.58% 的Java用户

二维数组排序使用以下方法，必须处理相等情况否则会报错java.lang.IllegalArgumentException: Comparison method violates its general contract!

        Arrays.sort(intervals,(o1,o2)->{if(o1[0]>o2[0]) return 1;else if(o1[0]<o2[0]) return -1;else return 0;});

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int findMinArrowShots(int[][] points) {if(points.length==0) return 0;//以后排序记得用这个方法更好，防止越界Arrays.sort(points, (o1, o2) -> o1[1]>o2[1]?1:-1);int preright=points[0][1];int ans=1;for (int i = 1; i < points.length; i++) {//相交的条件是某一个区间的右端在另一个区间之间，// 但是已经提前按右端排序，所以只要判断某一个区间的右端小于另一个区间的左端即可if(points[i][0]>preright){//上一边界不相交时，对当前区间射出一枝箭ans++;preright=points[i][1];}//和前一个区间相交的区间则直接略过}return ans;}
}

 

这篇关于452. 用最少数量的箭引爆气球(稍微总结一下贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---