貪心算法 452

自己做的比較差的答案是，對每一個元素的index0位置排序，然後計算後面的元素和前面的有沒有相交，不相交了就把arrow加1

public  int findMinArrowShots(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt(ints -> ints[0]));
        int minIndex = points[0][0];
        int maxIndex = points[0][1];
        int arrowNum = 0;

        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > minIndex){
                minIndex = points[i][0];
            }
            if (points[i][1] < maxIndex){
                maxIndex = points[i][1];
            }
            if (points[i][0] > maxIndex){
                arrowNum++;
                minIndex = points[i][0];
                maxIndex = points[i][1];
            }
        }
        return ++arrowNum;      

後來發現根本不應該對index0排序， 也滅有必要計算相交區間。其實隻要按index1排序，然後看後一個元素的index0是否小于目前的最小end。

Arrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));
        int end=points[0][1];
        int arrow=1;
        for(int i=0;i<points.length;i++)
        {
            if(points[i][0] > end)
            {
                arrow++;
                end=points[i][1];
            }
        }
        return arrow;