452. 用最少数量的箭引爆气球 - Java+Kotlin 贪心算法

原题地址：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/

题解

参考题解思路

将集合按照左边界升序排序，然后让箭的位置从左到右扫描，一直扫描到射爆的气球数量不再增加而是减少为止

由于事先已经按照左边界升序排序，箭扫描到的能引爆的气球必然是从左到右第一个能够引爆的气球，如果为了引爆该气球会让箭离开原来的一部分区间的范围，则后面的区间只会更糟糕，所以在这之前就是这一发箭能够射爆的最多气球数量

每次射爆气球时将其从集合中删除，重复循环一直到集合为空为止，扫描的次数就是需要箭矢的最少数量

这里偷懒用了List的Iterator进行迭代，时间复杂度会大一些

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    public int findMinArrowShots(int[][] points) {
        List<int[]> pointList= new LinkedList<>(Arrays.stream(points).toList());
        pointList.sort(Comparator.comparingInt((int[] a) -> a[0]));
        int cnt=0;
        int end;
        int[] tmp;
        Iterator<int[]> it;
        while (!pointList.isEmpty()){
            it=pointList.iterator();
            end=pointList.get(0)[1];
            while (it.hasNext()){
                tmp=it.next();
                if(tmp[0]<=end){
                    end=Math.min(end,tmp[1]);
                    it.remove();
                }else{
                    break;
                }
            }
            cnt++;
        } 
        return cnt;
    }
}

class Solution {
    fun findMinArrowShots(points: Array<IntArray>): Int {
        val pointList: MutableList<IntArray> = points.toMutableList()
        pointList.sortBy{it[0]}
        var cnt = 0
        var end: Int
        var tmp: IntArray
        var it: Iterator<IntArray>
        while (!pointList.isEmpty()) {
            it = pointList.iterator()
            end = pointList[0][1]
            while (it.hasNext()) {
                tmp = it.next()
                if (tmp[0] <= end) {
                    end = Math.min(end, tmp[1])
                    it.remove()
                } else {
                    break
                }
            }
            cnt++
        }
        return cnt
    }
}