算法训练营Day36(贪心-重叠区间）

都算是 重叠区间 问题，大家可以好好感受一下。 都属于那种看起来好复杂，但一看贪心解法，惊呼：这么巧妙！ 

还是属于那种，做过了也就会了，没做过就很难想出来。

不过大家把如下三题做了之后， 重叠区间 基本上差不多了

435. 无重叠区间 

435. 无重叠区间 - 力扣（LeetCode）

我这里先给一下为什么不取最大值的问题吧，我没看视频自己做的时候写的

如果用max的话，就是直接计算重复区间了，但是这道题还要删去，所以直接取右边界的最小值

答案：

这是我写的，和卡哥的也不一样，很简单

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

763.划分字母区间 

763. 划分字母区间 - 力扣（LeetCode）

题意难，听卡哥讲，easy很多。

class Solution {public List<Integer> partitionLabels(String s) {int [] hash = new int[27];//记录每个字母的最远位置for(int i = 0;i<s.length();i++){hash[s.charAt(i)-'a'] = i; }List<Integer> res = new ArrayList<>();//找left和rightint left= 0,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;}
}

56. 合并区间 

56. 合并区间 - 力扣（LeetCode）

这个很easy

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0])); List<int[]> res = new ArrayList<>();int start = intervals[0][0];int end = intervals[0][1];for(int i =1;i< intervals.length;i++){if(intervals[i][0]<=end){//更新右边界end = Math.max(end,intervals[i][1]);}else{//收集结果int [] subRes = new int[]{start,end};res.add(subRes);//更新 新的begin 和endstart = intervals[i][0];end = intervals[i][1];}}res.add(new int[]{start,end});return res.toArray(new int[res.size()][]);}
}