总结下重叠区间问题
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;
}
}LC 56. 合并区间
本题是LC 452 , LC 435同源的题 ，区别在于这里要把合并后的区间输出出来 ， 因此需要我们手动维护合并后的区间边界 left 和 right。而之前可以不管这个动态变化的边界 ，仅仅是计算count 。
写代码时要注意这一点，不能想当然的以为 right = max(nums[i][1] ， nums[i-1][1]) !!
class Solution {
private List<int[]> temp = new ArrayList<>();
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals , (a , b) ->(a[0] - b[0]));
int left = intervals[0][0];
int right = intervals[0][1];
for(int i = 1 ; i < intervals.length ; i ++){
if(intervals[i][0] > right){
temp.add(new int[]{left , right});
//只有当区间不重叠时， 才更新左边界
left = intervals[i][0];
right = intervals[i][1];
}else{
//重叠了，由于左边界本身是从小到大排序的，因此还是维持之前的left
right = Math.max(intervals[i][1] , right);
}
}
temp.add(new int[]{left , right});
int len = temp.size();
int[][] res = new int[len][2];
for(int i = 0 ; i < temp.size() ; i ++){
res[i] = temp.get(i);
}
return res;
}
}