代码随想录算法训练营 | 452. 用最少数量的箭引爆气球，435. 无重叠区间，763.划分字母区间

452. 用最少数量的箭引爆气球
题目链接：452. 用最少数量的箭引爆气球
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰452. 用最少数量的箭引爆气球
日期：2024-10-05

想法：对气球起点排序，没有重叠的箭头+1，有重叠得话将右边置为最小的右边。
Java代码如下：

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        int res = 1;
        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][1], points[i][1]);
            }
        }
        return res;
    }
}

435. 无重叠区间
题目链接：435. 无重叠区间
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰无重叠区间
日期：2024-10-05

想法：与气球很相似，选右边最短的就相当于删除了一次。
Java代码如下：

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

763.划分字母区间
题目链接：763.划分字母区间
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰划分字母区间
日期：2024-10-05

Java代码如下：

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> list = new LinkedList<>();
        int[] hash = new int[26];
        char[] chars = S.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            hash[chars[i] - 'a'] = i;
        }
        int left = 0;
        int right = 0;
        for (int i = 0; i < chars.length; i++) {
            right = Math.max(right, hash[chars[i] - 'a']);
            if (i == right) {
                list.add(i - left + 1);
                left = i + 1;
            }
        }
        return list;
    }
}