给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。
注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。
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; } }
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
class Solution { public List<Integer> partitionLabels(String S) { List<Integer> list = 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 idx = 0; int last = -1; for (int i = 0; i < chars.length; i++) { idx = Math.max(idx,edge[chars[i] - 'a']); if (i == idx) { list.add(i - last); last = i; } } return list; } }
给出一个区间的集合,请合并所有重叠的区间。
class Solution { public int[][] merge(int[][] intervals) { List<int[]> res = new LinkedList<>(); //按照左边界排序 Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0])); //initial start 是最小左边界 int start = intervals[0][0]; int rightmostRightBound = intervals[0][1]; for (int i = 1; i < intervals.length; i++) { //如果左边界大于最大右边界 if (intervals[i][0] > rightmostRightBound) { //加入区间 并且更新start res.add(new int[]{start, rightmostRightBound}); start = intervals[i][0]; rightmostRightBound = intervals[i][1]; } else { //更新最大右边界 rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]); } } res.add(new int[]{start, rightmostRightBound}); return res.toArray(new int[res.size()][]); } } }