代码随想录算法训练营第三十一天|435. 无重叠区间 ， 763.划分字母区间，56. 合并区间

 435. 无重叠区间 

代码随想录

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

 763.划分字母区间 

代码随想录

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

 56. 合并区间  

本题相对来说就比较难了。

代码随想录

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