海智算法训练营第三十五天 | 第八章 贪心算法 part05 | ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

今index.php/tags-41973.html" >���任务：

（）

1.非重叠区间问题（和气球一样）

2.划分字母区间

（）

3.合并区间

1.非重叠区间问题（和气球一样）

力扣题目链接

和射气球一样的做法，经典重叠区间基础问题

class Solution {    public int eraseOverlapIntervals(int[][] intervals) {        int sum = 0;        Arrays.sort(intervals , (o1,o2) -> Integer.compare(o1[0],o2[0]));        for (int i = 1; i = intervals[i-1][1])    continue;            else{                sum++;                intervals[i][1] = Math.min(intervals[i][1] , intervals[i-1][1]);            }        }        return sum;    }}

2.划分字母区间

力扣题目链接

这道题也很好想，先记录每个字母对应的最远的下标，然后每次循环不断更新右边界，直到循环到i等于右边界的时候就找到了一个边界，放入res集合就好了。

class Solution {    public List partitionLabels(String s) {        List res = new ArrayList();        int left = 0 , right = 0;        int[] hash = new int[26];        char[] str = s.toCharArray();        for (int i = 0; i    
3.合并区间
 
力扣题目链接
 
这道题也很好理解，相当于前两题的结合体，这里多用了一个left指针来记录最左边界
 
注意点：用此方法最后会有个left、right组合没有添加，要记得添加。 
 
class Solution {    public int[][] merge(int[][] intervals) {        List res = new ArrayList();        Arrays.sort(intervals , (o1,o2) -> Integer.compare(o1[0],o2[0]));        int left = intervals[0][0] , right = intervals[0][1];        for (int i = 1; i  right){                res.add(new int[]{left , right});                left = intervals[i][0] ;                right = intervals[i][1];            }else{                right = Math.max(right , intervals[i][1]);            }        }        res.add(new int[]{left,right});        return res.toArray(new int[res.size()][]);    }}
  
 
学习时长：2h
 
总结：此次学习了关于重叠区间更深的知识，对重叠区间类的题目更加的熟悉。