day36 贪心算法part5

435. 无重叠区间

中等
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

气球问题稍加改动就可ac

一个交叉区间里，最终只能保留一个，其他的全部要去掉。所以要移除的区间最小数量就是总数减去交叉区间数。

// 左边界排序直接求要移走的区间个数
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        int count = 0; // 注意是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], intervals[i - 1][1]);
                count++; // 有重叠就得挪走一个
            } else { // 无重叠
                // 无重叠不用处理，这里的else可以删掉
            }
        }
        return count;
    }
}

763. 划分字母区间

中等
提示
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = 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 max = 0; // 记录在以前出现过的最大的字母的下标
        int last = 0; // 题目划分字符段是用个数确定的，所以得记住上次划分的边缘
        for (int i = 0; i < chars.length; i++) {
            max = Math.max(max, hash[chars[i] - 'a']); // 看看当前字母下标和以前记录的max谁更大
            if (max == i) {
                result.add(i + 1 - last);
                last = i + 1;
            }
        }
        return result;
    }
}

56. 合并区间

中等
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

难点：找到重叠并不难，难在如何模拟合并。这个题想明白了也很简单，找到不重叠的区间就直接加到结果里，如果找到重叠的区间就记录这个重叠区间的左边界和右边界，把它当做一个区间来继续和下一个进行比较。

class Solution {
    public int[][] merge(int[][] intervals) {
        // 按左边界进行排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int leftBound = intervals[0][0]; // 左边界
        int rightBound = intervals[0][1]; // 最大右边界
        List <int[]> result = new LinkedList<>();

        for (int i = 1; i < intervals.length; i++) {
            if (rightBound < intervals[i][0]) { // 不重叠, 本题 = 也是重叠
                // 不重叠就加到结果里
                result.add(new int[] {leftBound, rightBound});
                // 更新左右边界
                leftBound = intervals[i][0];
                rightBound = intervals[i][1];
            } else { // 重叠
                // 左边界不用更新，已经是最左边了
                // 更新右边界
                rightBound = Math.max(rightBound, intervals[i][1]);
            }
        }
        // 注意这个！把最后一组加进去
        result.add(new int[]{leftBound, rightBound});
        return result.toArray(new int[result.size()][]); // 记住这个语法！！！
    }
}