LeetCode452. 用最少数量的箭引爆气球-Java&Go-贪心算法

• 算法
  • 1.贪心算法
  • 2.每次射箭都尽可能多射中气球，然后继续下一次射箭
    • 如何做到：
      • 首先给气球排序，按照结束坐标排序；
      • 每次射箭的位置就是气球的结束坐标，这样才能保证每次尽可能多的射中气球；
      • 然后每次射箭时检查后面的气球能否跟当前气球一起射中，直到不能跟当前气球一起射中时，新起一支箭；

public int findMinArrowShots(int[][] points) {
    if (points == null || points.length == 0) {
        return 0;
    }

    Arrays.sort(points, Comparator.comparingInt(a -> a[1]));
    int arrowPosition = points[0][1];
    int arrowCount = 1;
    for (int i = 0; i < points.length; i++) {
        if (points[i][0] > arrowPosition) {
            arrowPosition = points[i][1];
            arrowCount++;
        }
    }
    return arrowCount;
}

func findMinArrowShots(points [][]int) int {
    if points == nil || len(points) == 0 {
        return 0
    }

    sort.Sort(PointsBy2(points))
    arrowPosition, arrowCount := points[0][1], 1
    for i := 1; i < len(points); i++ {
        if points[i][0] > arrowPosition {
            arrowPosition, arrowCount = points[i][1], arrowCount + 1
        }
    }
    return arrowCount
}

type PointsBy2 [][]int
func (p PointsBy2) Len() int { return len(p) }
func (p PointsBy2) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p PointsBy2) Less(i, j int) bool {
    if p[i][1] < p[j][1] {
        return true
    } else {
        return false
    }
}