【贪心算法4】

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

链接: [link]( balloons/)

思路

这道题的第一想法就是如果气球重叠得越多那么用箭越少，所以先将气球按照开始坐标从小到大排序，遇到有重叠的气球，在重叠区域右边界最小值之前的区域一定需要一支箭，这道题有两个地方容易出错： 1.出现重叠区域，忘记更新最右边气球的有边界； 2.在重叠区域内射箭，即在下面提供的代码中else里执行res++； 这是我自己容易犯的错 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]( intervals/description/) 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.划分字母区间 链接: class Solution { public List partitionLabels(String s) { List 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; } } 56.合并区间 链接:

思路

这种题本质和【贪心算法4】的452和435一样的套路，这几道题都是判断区间重叠，区别就是判断区间重叠后的逻辑，本题是判断区间重贴后要进行区间合并。所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。 唯一需要考虑的是什么时候更新区间以及添加到ls中。 class Solution { public int[][] merge(int[][] intervals) { List ls = new ArrayList<>(); if(intervals.length == 1) return intervals; Arrays.sort(intervals,(a,b)->Integer.compare(a[0], b[0])); // 按照左边界排序 int start = intervals[0][0],end = intervals[0][1]; for(int i = 1;i end){ // 合并 ls.add(new int[]{start,end}); // 更新 start = intervals[i][0]; end = intervals[i][1]; } else{ end = Math.max(end,intervals[i][1]); } } ls.add(new int[]{start,end}); return ls.toArray(new int[ls.size()][]); } }