区间问题
1. 缩
LeetCode：452. 用最少数量的箭引爆气球
class Solution {
public int findMinArrowShots(int[][] points) {
int res = 0;
List<Point> list = new ArrayList<>();
for (int[] point : points) {
list.add(new Point(point[0], point[1]));
}
Collections.sort(list, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
if (o1.left != o2.left){
return Long.compare(o1.left, o2.left);
}
return Long.compare(o1.right, o2.right);
}
});
for (int i = 0; i < list.size(); i++) {
Point point = list.get(i);
res++;
while (i + 1 < list.size() && point.right >= list.get(i + 1).left){ // 尽量去缩进
point.left = Math.max(point.left, list.get(i + 1).left);
point.right = Math.min(point.right, list.get(i + 1).right);
i++;
}
}
return res;
}
}
class Point{
long left;
long right;
public Point(long left, long right) {
this.left = left;
this.right = right;
}
}