【贪心算法4】

力扣452.用最少数量的剪引爆气球

链接: link

思路

这道题的第一想法就是如果气球重叠得越多那么用箭越少，所以先将气球按照开始坐标从小到大排序，遇到有重叠的气球，在重叠区域右边界最小值之前的区域一定需要一支箭，这道题有两个地方容易出错：
1.出现重叠区域，忘记更新最右边气球的有边界；
2.在重叠区域内射箭，即在下面提供的代码中else里执行res++；
这是我自己容易犯的错

方法1:

class Solution {public int findMinArrowShots(int[][] points) {if (points.length == 0)return 0;Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int res = 1;// 气球数组不为0，至少需要一支箭for (int i = 1; i < points.length; i++) {// 当前气球开始位>前一个气球的结束位置if (points[i][0] > points[i - 1][1]) {res++;} else {// 否则当前气球和前一个气球挨着// 更新当前气球的有边界，瑜前一个气球比较// 更新是为了避免和后一个气球比较的时候重复射箭points[i][1] = Math.min(points[i][1], points[i - 1][1]);}}return res;}
}

435.无重叠区间
链接: link

class Solution {public int eraseOverlapIntervals(int[][] intervals) {if (intervals.length == 1)return 0;// 按照右边界排序，从前向后遍历Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));int cnt = 1;// 统计重合区域for (int i = 1; i < intervals.length; i++) {// 当前节点的左边界<前一个节点的右边界，一定有重合if (intervals[i][0] < intervals[i - 1][1]) {// 更新当前节点右边界intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);} else {// 当前节点和前一个节点没有重合cnt++;}}return intervals.length - cnt;}
}

相似题型

763.划分字母区间
链接: link

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> ls = new ArrayList<>();int[] edge = new int[26];char[] chars = s.toCharArray();for (int i = 0; i < chars.length; i++) {edge[chars[i] - 'a'] = i; // 记录每个字母最大边界}int left = 0, right = 0;for (int i = 0; i < chars.length; i++) {right = Math.max(right, edge[chars[i] - 'a']);if (i == right) {ls.add(i - left + 1);left = right + 1;}}return ls;}
}