Day36｜贪心算法part05：435. 无重叠区间、763.划分字母区间、56. 合并区间

435. 无重叠区间

有了上题射气球的因子，这题也就有思路了，反正无脑排序就行了：

• 首先将所有区间按照end的大小从小到大排序；
• 选取最早end为起始x_end
• 遍历所有区间，如果该区间的start比end大（可重叠），说明不重叠，count++，该区间的end重新定义为end

（以上就是不重叠区间的用法，用总区间数 - 不重叠区间数就是要删除的区间树）

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));int count = 1;int x_end = intervals[0][1];for(int[] point : intervals){if(point[0] >= x_end){//这里是等于，因为顶点重叠不算重叠（跟气球那题不一样）count++;x_end = point[1];}}return intervals.length - count;}
}

763. 划分字母区间

贪心就是找到每个字符最后出现的位置，如果如果找到之前遍历过的所有字母的最远边界, 当前i等于边界，就加入结果集再把left+ 1:

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

• 初始化一个右边界right，是i之前所有字母的最远边界的最大值，左边界left用于计算区间长度。

56. 合并区间

• 这题的关键点在于通过更新resList中的元素（特别是终点end）而不是创建新元素直接加入。

class Solution {public int[][] merge(int[][] intervals) {LinkedList<int[]> res = new LinkedList<>();Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));res.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] <= res.getLast()[1]) {int start = res.getLast()[0];int end = Math.max(intervals[i][1], res.getLast()[1]);//实际上就是更新res的最后一个元素res.removeLast();res.add(new int[]{start, end});}else {res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);}
}