452. 用最少数量的箭引爆气球(leetcode)
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
思路是排序,方便计算气球重叠,难点是在重叠时更新右边界,更新为 两个区间的最右重合点,因为这个点是最少一支箭就可以射掉两个气球的最右点,再去下个循环判断区间重合
class Solution {
public int findMinArrowShots(int[][] points) {
// 思路:按照气球起始位置进行排序,让气球相邻,方便计算出重叠的气球数
Arrays.sort(points,(a,b)-> Integer.compare(a[0], b[0]));
int res=1; // 题给出points.length>=1,因此必须要有一支箭
for(int i=1;i<points.length;i++)
{
if(points[i-1][1] < points[i][0])res++; //气球不重叠,此时必须要一支箭
else
{
// 气球重叠,直接跳过重叠的气球
// 难点:把重叠的气球右边界更新,更新为最小的一支箭就可以射掉的最右边界
// 即两个区间的最右重合点
points[i][1]=Math.min(points[i-1][1],points[i][1]);
}
}
return res;
}
}