代码随想录刷题随记31-贪心5

435. 无重叠区间

leetcode链接
按照右边界排序，从左向右记录非交叉区间的个数。
此时问题就是要求非交叉区间的最大个数。
这里记录非交叉区间的个数还是有技巧的，如图：

左边界排序可不可以呢？
也是可以的，只不过 左边界排序我们就是直接求 重叠的区间，count为记录重叠区间数。

因为按照右边排序，从左到右进行遍历来到一个位置可以在遍历到一个位置以后，得知之前所有区间右端的最小值。所以就知道有哪些区间和自己不重合。
如果按照左区间排序，就知道左侧最小值可以知道

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

763. 划分字母区间

leetcode链接
统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

class Solution {
    public List<Integer> partitionLabels(String s) {
       List<Integer> ret=new LinkedList<>();
       int [] bag=new int[26];
       char[] chars = s.toCharArray();
       for(int i=0;i<s.length();i++){
          bag[chars[i]-'a']=i;
       }
       int last=-1;
       int idx=0;
       for(int i=0;i<chars.length;i++){
           idx=Math.max(idx,bag[chars[i]-'a']);
           if(idx==i){
            ret.add(i-last);
            last=i;
           }
       }
       return ret;
    }
}

56. 合并区间

leetcode链接
本题的本质其实还是判断重叠区间问题。
和452. 用最少数量的箭引爆气球 (opens new window)和 435. 无重叠区间 (opens new window)都是一个套路。

class Solution {
    public int[][] merge(int[][] intervals) {
         Arrays.sort(intervals,(a,b)->{return Integer.compare(a[0], b[0]);});
         int start=intervals[0][0];
         int end=intervals[0][1];
         List<int[]> ret=new LinkedList<>();
         int flag=-1;
         for(int i=1;i<intervals.length;i++){
             if(intervals[i][0]<=intervals[i-1][1]){
                //重合
                //更新end
                intervals[i][1]=Math.max(intervals[i][1],intervals[i-1][1]);
             }
             else{
                //不重合收集结果
                int [] tmp=new int[2];
                tmp[0]=start;
                tmp[1]=intervals[i-1][1];
                ret.add(tmp);
                start=intervals[i][0];
             }
         }
         int [] tmp=new int[2];
         tmp[0]=start;
         tmp[1]=intervals[intervals.length-1][1];
         ret.add(tmp);
            
         return ret.toArray(new int[ret.size()][]);
    }
}