[leetcode hot 150]第四百五十二题，用最少数量的箭引爆气球

题目：

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

 

 解决这个问题的关键是要找到尽可能多的重叠区间。可以使用贪心算法：

1. 首先，按照气球的结束坐标（xend）对所有气球进行排序。
2. 然后，从第一个气球开始，射出一支箭。
3. 看这支箭能否引爆下一个气球，如果能，继续看下一个。
4. 如果不能，就需要再射出一支箭。

import java.util.Arrays;
import java.util.Comparator;public class no_452 {public static void main(String[] args) {int[][] quJian = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};System.out.println(findMinArrowShots(quJian));}public static int findMinArrowShots(int[][] points) {if (points == null || points.length == 0) return 0;Arrays.sort(points, Comparator.comparingInt(a -> a[1]));int arrowPos = points[0][1];int arrowCount = 1;for (int i = 1; i < points.length; i++) {if (points[i][0] > arrowPos) {arrowCount++;arrowPos = points[i][1];}}return arrowCount;}
}