前言

问题转换，将繁杂的故事抛弃，取出其中的核心问题。通过用最少数量的箭引爆气球练习贪心之区间交集。

一、用最少数量的箭引爆气球

二、贪心–区间交集

package everyday;import java.util.Arrays;
import java.util.Comparator;// 用最少数量的箭引爆气球。
public class FindMinArrowShots {/*target：讲一半天故事，就是区间合并，合并定义为交集，最后看有多少不相交的区间。M1：将points按start点排序，用end值去和next的start比较，记录剩余区间的同时，并更新end值。*/public int findMinArrowShots(int[][] points) {// 排序。Arrays.sort(points, Comparator.comparingInt(o -> o[0]));// Arrays.stream(points).sorted(Comparator.comparingInt(o -> o[0]));// 获取end值，不断更新剩余区间，并更新end值。int end = points[0][1];int n = points.length;int rs = n;for (int i = 1; i < n; i++) {if (end >= points[i][0]) {--rs;end = end <= points[i][1] ? end : points[i][1];} else {end = points[i][1];}}return rs;}
}

总结

1）问题转换。
2）区间交集。

参考文献

[1] 用最少数量的箭引爆气球