(贪心05) 无重叠区间 划分字母区间 合并区间

一、无重叠区间

力扣第435题

第一种方法：

个人思路：

        按照区间左边界排序，然后从左开始遍历，每遍历到一个区间就要保证该区间之前的集合为不重叠区间（贪心，局部最优解）。

        难点在于如何把新遍历到的区间整合为不重叠，分情况讨论。

代码如下：

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

时间复杂度：O(nlogn)

空间复杂度：O(1)

第二种方法：

思路：

        统计不重叠区间，最后区间总和减去不重叠区间个数就等于重叠区间个数。

代码如下：

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

时间复杂度：O(nlogn)

空间复杂度：O(1)

二、划分字母区间

力扣第763题

思路：

        在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。 

        可以分为如下两步：

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

代码如下：

class Solution {public List<Integer> partitionLabels(String s) {int[] hash = new int[27];for(int i = 0; i < s.length(); i++) {char c = s.charAt(i);hash[c - 'a'] = i;}List<Integer> list = new ArrayList<>();int left = 0;int right = 0;for(int i = 0; i < s.length(); i++) {right = Math.max(right, hash[s.charAt(i) - 'a']);if(i == right) {list.add(right - left + 1);left = i + 1;}}return list;}
}

时间复杂度:O(n)

空间复杂度:O(1)

三、合并区间

力扣第56题  

代码如下：

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

时间复杂度：O(nlogn);

空间复杂度：O(1);