435. 无重叠区间
这道题和 452. 用最少数量的箭引爆气球 基本上一模一样，是一个思路。至少要删除几个区间才能使剩下的区间不重叠，其实就是在统计有几个区间重叠了。
public int eraseOverlapIntervals(int[][] intervals) {
// 先按区间的起始位置排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
// 维护右边界
int end = intervals[0][1];
int result = 0;
for (int i = 1; i < intervals.length; i++) {
int[] curr = intervals[i];
if (curr[0] < end) {
// 重叠
result++;
// 为什么要取较小的作为边界
// 这就是我们贪心的思路，取最小的就意味着删掉交叉、但右边界较大的区间
// 这样可以减少较大区间对后续区间交叉的概率
// 即删除交叉区间中较长（右边界较大）的那一个，减少对后续区间的影响
end = Math.min(end, curr[1]);
} else {
end = curr[1];
}
}
return result;
}763. 划分字母区间
这个题需要理解一段话 “同一字母最多出现在一个片段中”，再加上题目要求不能更换字符顺序，因此可以理解为寻找遍历字符的最后出现的位置，如：“ababcbacadefegdehijhklij”，先遍历一遍，统计各个字符最后出现的位置，然后再遍历一遍，例如访问字符 a 时，它最终出现的下标是 8，那么第一个区间至少得到下标 8，再访问字符 b，如果它最终出现的下标是 10，那么第一个区间至少得到下标 10，加入后面的字符最终出现的位置没有超过 10 的，那么当遍历到 10 时就可以统计这段区间的长度了，然后继续按照上面的逻辑遍历。
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new LinkedList<>();
// 记录每个字符最远出现的位置
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i), i);
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.get(c) > end) {
end = map.get(c);
}
if (i == end) {
res.add(i - start + 1);
start = i + 1;
}
}
return res;
}
}因为是 26 个小写字母，改用数组效率会更高。
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new LinkedList<>();
// 记录每个字符最远出现的位置
int[] map = new int[27];
for (int i = 0; i < s.length(); i++) {
map[s.charAt(i) - 'a'] = i;
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map[c - 'a'] > end) {
end = map[c - 'a'];
}
if (i == end) {
res.add(i - start + 1);
start = i + 1;
}
}
return res;
}
}据说和两个跳跃游戏是类似的思路？
56. 合并区间
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][];
LinkedList<int[]> list = new LinkedList<>();
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
int start = intervals[0][0];
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
int[] curr = intervals[i];
if (curr[0] <= end) {
// 重叠，合并，只用更新右边界，即取较大的 end
end = Math.max(end, curr[1]);
} else {
// 不重叠，收集结果，然后记录新的 start、end
list.add(new int[]{start, end});
start = curr[0];
end = curr[1];
}
}
// 加上最后一个区间
list.add(new int[]{start, end});
// int[][] res = new int[list.size()][];
// int i = 0;
// for (int[] e: list) {
// res[i++] = e;
// }
// return res;
return list.toArray(new int[list.size()][]);
}
}这个题和 452. 用最少数量的箭引爆气球 以及上面的 “无重叠区间” 的思路是一样的。