代码随想录第三十天|无重叠区间| 划分字母区间| 合并区间

今天三道都是重叠区间问题，重叠区间问题第一步就是先对数组进行排序，才能进行后续操作。

无重叠区间

这一题和昨天的最少多少支箭射爆气球的解法是相同的，判断相邻区间是否重叠，若两个区间重叠了则找出重叠区间最小右边界，更新区间去和下一个区间做判断。进行重复操作。因为重叠了就需要删除一个区间，更新区间就相当于删除区间，再和下一个区间做比较。

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

划分字母区间

划分字母区间。就是从头开始遍历，找到最远的相同字母的下标，什么是最远呢？就是在最远字母所包含的区间内的所有字母及其相同字母只在这个区间出现过了，且下标都小于最远下标。从头字母到这个最远相同字母下标的区间就是所求的区间。

那么怎么求最远下标呢？这里需要想到哈希数组，因为这里都是字母，元素有限，可以将每个字母元素的下标映射到哈希数组中，因为每个位置都只对应着一个元素，遇到相同字母时就会刷新哈希数组中的下标元素，找到每个字母所对应的最远下标。

这里再设置一个left和right指针用来记录区间长度。left首先指向头部，right指向头部元素，记录下当前字母的最远下标，往后移动一次就刷新一次。当right指针所指向的字母下标等于该字母的最远下标时，就是符合条件的区间。

class Solution {
    public List partitionLabels(String s) {
        int[] hash=new int[27];//哈希数组，哈希思想统计最远下标
        for(int i=0;i
            hash[s.charAt(i)-'a']=i;
        }
        List result=new ArrayList();
        int left=0,right=0;
        for(int i=0;i
            right=Math.max(right,hash[s.charAt(i)-'a']);
            if(right==i){
                result.add(right-left+1);
                left=i+1;
            }
        }
        return result;
    }
}

合并区间

合并区间和第一题也类似，只是合并区间的时候要找重叠区间的最大右边界，然后更新当前区间，删除结果集中的上一个末尾元素，再将更新后的加入到结果集中。若不重叠，则直接加入结果集中。然后重复操作。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            if(a[0]==b[0]){
                return a[1]-b[1];
            }else{
                return a[0]-b[0];
            }
        });
        List<int[]> result=new ArrayList();
        result.add(intervals[0]);
        for(int i=1;i
            if(intervals[i][0]<=intervals[i-1][1]){
                intervals[i][1]=Math.max(intervals[i-1][1],intervals[i][1]);
                intervals[i][0]=intervals[i-1][0];
                result.remove(result.size()-1);
                result.add(intervals[i]);
            }else{
                result.add(intervals[i]);
            }
        }
        int[][] arr=new int[result.size()][];
        result.toArray(arr);
        return arr;
    }
}