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;

    }
}