贪心算法 Part04

总结下重叠区间问题

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

和

LC 435. 无重叠区间

本质上是一样的。

LC 452. 用最少数量的箭引爆气球 是求n个区间当中 ， 区间的种类数量 k。此处可以理解为，重叠在一起的区间属于同一品种，没有重叠的区间当然就是另一个品种 ， 最少数量的箭，也就是区间总的种类数量k ， 有k种区间 ，最少就得花k只剑，每种区间耗费一支。

而 LC 435. 无重叠区间 ， 问使得区间之间不重叠，要移除的区间数量，可以这样思考：

n个区间当中，有k种区间（区间的种类数量 k）。要使得区间之间不重叠 ， 也就是说每个种类的区间只能保留一种！（因为有重叠的区间属于同一个品种）

因此 要移除的区间数量 就是总的区间数 n 减去区间种类的数量 k。

这两个题是同一个模板！

给出无重叠区间的代码

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

763.划分字母区间

题目描述：

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

思路：

1.先遍历字符串 ，把每个字母出现的最大的索引存到一个哈希表中

2.再遍历字符串，此时我们就要去划分字符串了。划分的过程如下：

先初始化子区间的左右边界 left ， right 初始化为0 ， 0

遍历的时候 ，动态更新当前区间的最大右边界 ，而当恰好此时的索引 i 等于右边界时 ，就划分出一个子区间了，该子区间长度为 right - left + 1。 划分完毕后 ，left 需要更新为 i + 1 ，然后继续遍历，重复此过程。。。。

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> res = new ArrayList<>();int[] hash = new int[26];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){res.add(right - left + 1);left = i + 1;}}return res;}
}