435. 无重叠区间
有了上题射气球的因子,这题也就有思路了,反正无脑排序就行了:
- 首先将所有区间按照end的大小从小到大排序;
- 选取最早end为起始x_end
- 遍历所有区间,如果该区间的start比end大(可重叠),说明不重叠,count++,该区间的end重新定义为end
(以上就是不重叠区间的用法,用总区间数 - 不重叠区间数就是要删除的区间树)
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int count = 1;
int x_end = intervals[0][1];
for(int[] point : intervals){
if(point[0] >= x_end){//这里是等于,因为顶点重叠不算重叠(跟气球那题不一样)
count++;
x_end = point[1];
}
}
return intervals.length - count;
}
}
763. 划分字母区间
贪心就是找到每个字符最后出现的位置,如果如果找到之前遍历过的所有字母的最远边界, 当前i等于边界,就加入结果集再把left+ 1:
class Solution {
private int[] alphabet = new int[26];
private List<Integer> resList = new ArrayList<>();
public List<Integer> partitionLabels(String s) {
for(int i = 0 ; i < s.length(); i++){
alphabet[s.charAt(i) - 'a'] = i;
}
int left = 0, right = 0;
for(int i = 0; i < s.length(); i++){
right = Math.max(right, alphabet[s.charAt(i) - 'a']);
if(i == right){
resList.add(i - left + 1);
left = i + 1;
}
}
return resList;
}
}
- 初始化一个右边界right,是i之前所有字母的最远边界的最大值,左边界left用于计算区间长度。
56. 合并区间
- 这题的关键点在于通过更新resList中的元素(特别是终点end)而不是创建新元素直接加入。
class Solution {
public int[][] merge(int[][] intervals) {
LinkedList<int[]> res = new LinkedList<>();
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
res.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= res.getLast()[1]) {
int start = res.getLast()[0];
int end = Math.max(intervals[i][1], res.getLast()[1]);
//实际上就是更新res的最后一个元素
res.removeLast();
res.add(new int[]{start, end});
}
else {
res.add(intervals[i]);
}
}
return res.toArray(new int[res.size()][]);
}
}