算法训练营day31 | {452.用最少数量的箭引爆气球, 435.无重叠区间, 763.划分字母区间}

第八章贪心算法part04，都是重叠区间问题。

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

• 题目链接：452.用最少数量的箭引爆气球
• 文档讲解：代码随想录
• 视频讲解：贪心算法，判断重叠区间问题 | LeetCode：452.用最少数量的箭引爆气球
• 状态：直观上在重叠区间最多的地方射箭，就是贪心所在，代码怎么实现？

1.1 解题分析

难点在于如何模拟气球被射爆的过程，例如如何判断两个气球重叠，如何判断下一个气球也重叠？

▶

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

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, (o1, o2)->Integer.compare(o1[0], o2[0]));
        int result = 1;
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > points[i - 1][1]) result++;
            else {
                points[i][1] = Math.min(points[i][1], points[i - 1][1]);
            }
        }
        return result;
    }
}

• Java Comparator 写法要注意 int溢出问题，Integer.compare(a, b)是正确的写法，因为它的实现逻辑等价于：

  if (a < b) return -1;
  if (a > b) return 1;
  return 0;

不做减法，永不溢出，关于排序推荐使用Integer.compare(a, b)或Long.compare(a, b)。

435. 无重叠区间

• 题目链接：435.无重叠区间
• 文档讲解：代码随想录
• 视频讲解：贪心算法，依然是判断重叠区间 | LeetCode：435.无重叠区间
• 状态：和上一题差不多，按左边界排序后，遇到重叠区间，记录一下要删一个就行，不用真删除。

2.1 解题分析

▶

435. 无重叠区间

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 1) return 0;
        Arrays.sort(intervals, (o1, o2)->Integer.compare(o1[0], o2[0]));
        int result = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                result++;
                intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        return result;
    }
}

763. 划分字母区间

• 题目链接：763.划分字母区间
• 文档讲解：代码随想录
• 视频讲解：贪心算法，寻找最远的出现位置！ LeetCode：763.划分字母区间
• 状态：没什么思路，记录每个字母最远位置的做法很妙。

3.1 解题分析

题目要求同一个字母最多出现在一个片段中，怎么能把同一个字母圈在同一个区间中呢？需要记录每一个字母的最远位置。

具体地，解题思路分为两步：

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点。

▶

763. 划分字母区间

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] hash = new int[26];
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a'] = i;
        }
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            right = Math.max(right, hash[s.charAt(i) - 'a']);
            if (i == right) {
                result.add(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
}