代码随想录训练营Day36：● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

435. 无重叠区间

题目链接

https://leetcode.cn/problems/non-overlapping-intervals/description/

题目描述

在这里插入图片描述

思路

直接统计重叠区间的个数，就是需要删除的个数

在这里插入图片描述

public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)-> Integer.compare(a[0],b[0]));
        if(intervals.length == 0) return 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],intervals[i-1][1]);
            }
        }
        return count;
    }

763.划分字母区间

题目链接

https://leetcode.cn/problems/partition-labels/description/

题目描述

在这里插入图片描述

思路

在这里插入图片描述
对于上边的字符串 s = “ababcbacadefegde”
最开始先包含 a ,根据题目要求，需要把所有的 a 都囊括进一个区间里边，所以找到最远的 a 为下标 8 的位置，但是在囊括 a 的同时，需要把 b c 囊括进来，所以需要再次找 b c 的最远位置，统计过 a b c 的最远位置之后进行比较，这一个区间的最远位置就是 8 ，因此 8 之前就为一个分割区间

class Solution {
    public List<Integer> partitionLabels(String s) {
        ArrayList<Integer> list = new ArrayList<>();
        //先统计每个字符出现的最远位置
        //遍历字符串
        int[] hash = new int[26];
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a'] = i; 
        }
        //定义区间的左右边界
        int left = 0,right = 0;
        for (int i = 0; i < s.length(); i++) {
            right = Math.max(right,hash[s.charAt(i) - 'a']);
            //i==right  说明已经到了这个字符串的最右边
            if(i==right){
            //将长度加到结果列表中
                list.add(right-left+1);
                left = i+1;
            }
        }
        return list;
    }
}

56. 合并区间

题目链接

https://leetcode.cn/problems/merge-intervals/description/

题目描述

在这里插入图片描述

思路

在这里插入图片描述
思路在代码注释中均有描述

public int[][] merge(int[][] intervals) {
        //存放最后的结果
        ArrayList<int[]> list = new ArrayList<>();
        if(intervals.length==0) return new int[0][];
        //按照左边界进行排序
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));
        list.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] <= list.get(list.size()-1)[1]){
                //说明重叠了，需要进行合并
                //区间的最小边界肯定是已经存进去的左边界，所以不用做更新
                //需要更新右边界，将当前元素和已经存进去的右边界进行比较，取大的一方
                list.get(list.size()-1)[1] = Math.max(intervals[i][1],list.get(list.size()-1)[1]);
            }else {
                //没有重叠，直接添加到结果中，不做任何操作
                list.add(intervals[i]);
            }
        }
        return list.toArray(new int[list.size()][]);
    }