贪心算法 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;