第八章 贪心算法 part04

今天的三道题目，都算是 重叠区间 问题，大家可以好好感受一下。 都属于那种看起来好复杂，但一看贪心解法，惊呼：这么巧妙！
这种题还是属于那种，做过了也就会了，没做过就很难想出来。
不过大家把如下三题做了之后， 重叠区间 基本上差不多了

452. 用最少数量的箭引爆气球

文章讲解

思路

• 存在重叠的气球就一起射
• 不用移除气球数组的元素，只需要统计箭的数量
• 将数组按照起始位置排序，如果气球重叠了，那么右边边界的最小值
• 算法步骤
  • 排序：
    首先按气球的结束位置（points[i][1]）对所有气球进行排序。这是因为我们希望尽可能长地利用每支箭的有效范围。
  • 初始化：
    我们至少需要一支箭，所以初始化 arrows = 1。
    end 用来记录当前箭的有效射程的结束位置，初始为第一个气球的结束位置 points[0][1]。
  • 遍历气球：
    从第二个气球开始，逐个检查气球。
    如果当前气球的起始位置 points[i][0] 大于 end，这意味着当前气球与之前的气球不重叠，需要新增一支箭。
    如果当前气球与之前的气球重叠（即 points[i][0] <= end），它们可以共享同一支箭。

class Solution {
    public int findMinArrowShots(int[][] points) {
        //按照结束位置从小到大排序
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        int result = 1;
        for(int i = 1; i < points.length; i++){
            // 气球 i 的起始位置 points[i][0] 大于前一个气球 i-1 的结束位置 points[i - 1][1]，说明这两个气球不重叠，也不相邻。
            if(points[i][0] > points[i-1][1]){ 
                result++;
            }else{
                //注意这里的逻辑是更新气球最小右边界
                points[i][1] = Math.min(points[i][1], points[i-1][1]);
            }
        }
        return result;
    }
}

435. 无重叠区间

文章讲解

思路

• 按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 1;
        int end = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(end <= intervals[i][0]){
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.length - count;
    }
}

763.划分字母区间

文章讲解

思路

• 解法1：
  1.统计每一个字符最后出现的位置
  2.从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
• 解法2：
  将区间按左边界从小到大排序，找到边界将区间划分成组，互不重叠。找到的边界就是答案。

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new LinkedList<>();
        int[] edge = new int[26];
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++){
            edge[chars[i] - 'a'] = i;//如：edge[0] = 2，表示字符 'a' 最后出现的位置是索引 2。
        }
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.length(); i++){
            // 更新最远边界 right：因为对于每个字符 chars[i]，edge[chars[i] - 'a'] 给出了该字符的最后出现位置。
            // right = Math.max(right, edge[chars[i]-'a']) 
            // 这一行代码确保 idx 始终表示从当前字符到目前为止，所有字符的最远边界。
            right = Math.max(right, edge[chars[i]-'a']);
            if(i == right){
                result.add(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
}

只写了第一种，有时间写第二种