452. 用最少数量的箭引爆气球（中等）

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

1. 题目描述

题目中转：452. 用最少数量的箭引爆气球

2.详细题解

    引爆所有气球，弓箭数要最少，那么每支弓箭尽量多的引爆气球，采用贪心策略。对于重叠（仅边界重合也是重叠此题中）的区间，仅需一只弓箭即可引爆即可，因此问题转换为对于重叠的区间仅留一个区间即可，其它区间移除即可，最终留下的区间数则是所需的最少得弓箭数。和435.无重叠空间（中等）题目类似，但有区间在于仅边界重合的也可仅用一只弓箭解决，因此对于边界重合的也要视为叠加。

3.代码实现

3.1 Python

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort(key=lambda x:(x[1],x[0]))res = 1right = points[0][1]for l,r in points[1:]:if l > right:res += 1right = rreturn res

3.2 Java

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, new Comparator<int[]>(){public int compare(int[] left, int[] right){if (left[1] >= right[1]){return 1;}else{return -1;}}});int ans = 1;int right = points[0][1];for (int i=0;i<points.length;i++){if (points[i][0] > right){ans++;right = points[i][1];}}return ans;}
}

  Java程序有个细节需要注意，注意看区间的取值范围，因此在排序时不能再直接比较两个数据的差值，因为一旦一个负数或者整数相减，可能会超出int的取值范围，如测试案例[[-2147483646,-2147483645],[2147483646,2147483647]]

  执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一般是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络环境、当前提交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code

这篇关于452. 用最少数量的箭引爆气球（中等）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---