2021/04/25
思维方法
想象有一个数轴，有许多闭区间在这个数轴上，有些地方覆盖到了，有些地方没有覆盖到，我们要做的是，把能连起来的闭区间们合并一个大的闭区间。
解法一
我们对所有这些区间按照起始坐标排序，这样我们就可以从数轴的最左边向右遍历这些区间了，如果可以融合的就融合成一个区间，不能融合的就增加一个新的区间。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(arr -> arr[0]));
LinkedList<int[]> res = new LinkedList<>();
for (int[] cur : intervals) {
if (res.isEmpty()) {
res.add(cur);
} else {
int[] top = res.getLast();
// 如果区间不相交
if (top[0] > cur[1] || top[1] < cur[0]) {
res.add(cur);
} else {
// 如果区间相交，则融合成一个新的区间
int[] newRange = {Math.min(top[0], cur[0]), Math.max(top[1], cur[1])};
res.removeLast();
res.add(newRange);
}
}
}
return res.toArray(new int[res.size()][]);
}
}
解法一的改进
解法一列出来的区间是否相交的条件，以及两个相交区间融合成一个新区间的写法，是比较通用的，但此题因为已经对区间按起始坐标进行了排序，对于区间 $[x_i, y_i]$ 和区间 $[x_{i+1}, y_{i+1}]$，一定有 $x_i \leq x_{i+1}$，所以：
- 区间不相交时一定是第二个区间在第一个区间的右边
- 两个区间融合成的新区间的起始坐标一定是第一个区间的起始坐标。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(arr -> arr[0]));
LinkedList<int[]> res = new LinkedList<>();
for (int[] cur : intervals) {
if (res.isEmpty()) {
res.add(cur);
} else {
int[] top = res.getLast();
if (top[1] < cur[0]) { // ← 条件减弱
res.add(cur);
} else { // ↓ 坐标确定
int[] newRange = {top[0], Math.max(top[1], cur[1])};
res.set(res.size() - 1, newRange);
}
}
}
return res.toArray(new int[res.size()][]);
}
}
也可以简化一下代码，看起来短了很多：
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(arr -> arr[0]));
LinkedList<int[]> res = new LinkedList<>();
for (int[] cur : intervals) {
if (res.isEmpty() || res.getLast()[1] < cur[0]) {
res.add(cur);
} else {
res.getLast()[1] = Math.max(res.getLast()[1], cur[1]);
}
}
return res.toArray(new int[res.size()][]);
}
}
继续优化
如果我们对区间不只是按照起始坐标排序，在起始坐标相同的情况下，再根据结尾坐标排倒序，如图：
[[1,5], [1,4], [1,3], [2,6], [2,3], [3,1]]
我们扫描到 [1,5] 的时候，就可以跳过所有起始坐标为 1 的区间了
class Solution {
public int[][] merge(int[][] intervals) {
// Java 的 Comparator 是可链式组合的
Arrays.sort(intervals, Comparator.comparingInt((int[] arr) -> arr[0])
.thenComparingInt(arr -> -arr[1]));
LinkedList<int[]> res = new LinkedList<>();
for (int i = 0; i < intervals.length; i++) {
int[] cur = intervals[i];
if (res.isEmpty()) {
res.add(cur);
} else { // 此时 i 一定大于 0
if (intervals[i - 1][0] == cur[0]) {
continue;
}
int[] top = res.getLast();
if (top[1] < cur[0]) {
res.add(cur);
} else {
int[] newRange = {top[0], Math.max(top[1], cur[1])};
res.set(res.size() - 1, newRange);
}
}
}
return res.toArray(new int[res.size()][]);
}
}
简化一下代码，可以看得更清晰，为啥性能没多大提升。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt((int[] arr) -> arr[0])
.thenComparingInt(arr -> -arr[1])); // 1. 排序开销更大了
LinkedList<int[]> res = new LinkedList<>();
int[] prev = null;
for (int[] cur : intervals) {
if (res.isEmpty() || res.getLast()[1] < cur[0]) {
res.add(cur);
} else {
if (prev[0] == cur[0]) continue; // 2. 减少了一个赋值操作，下面的 Max 也有比较操作
res.getLast()[1] = Math.max(res.getLast()[1], cur[1]);
}
prev = cur; // 3. 这里增加了一个赋值操作
}
return res.toArray(new int[res.size()][]);
}
}