vvrf / DSA.log

问题拆解

给一堆区间，把所有互相重叠的合并成一个，返回互不重叠的结果。麻烦在于重叠关系是传递的：[1,3] 和 [2,6] 重叠，[2,6] 又和 [5,8] 重叠，三个要并成一个。如果对每一对区间都去检查重叠，是 O(n²) 的比较，还要处理合并后再次触发合并的连锁反应。

先按左端点排序，局面就完全不同了：逐个扫描时，能和当前区间重叠的区间左端点都不比它大，也就是说，它的“合并对象”只可能出现在已经处理过的部分里。更进一步，只可能是结果集里最后那一个。

排序保证了重叠只发生在相邻的扫描顺序之间：新区间若与结果集里更早的区间重叠，那个区间和最后一个区间之间就不可能断开——矛盾。所以每一步只需回头看一眼。

排序后与结果集尾部合并

严格论证一下“只看最后一个”为什么够：结果集里的区间互不重叠且按左端点递增，所以最后一个区间的左端点大于前面所有区间的右端点。而新区间 cur 的左端点不小于最后一个的左端点（排序保证），因此 cur 也够不着前面任何区间。判断就简化成一条：cur[0] <= last[1] 则重叠，把 last[1] 扩到两者较大值；否则 cur 自成一段。

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> merged = new ArrayList<>();
    for (int[] cur : intervals) {
        int last = merged.size() - 1;
        if (!merged.isEmpty() && cur[0] <= merged.get(last)[1]) {
            // 有重叠，扩展右端点；注意 cur 可能被 last 完全包住
            merged.get(last)[1] = Math.max(merged.get(last)[1], cur[1]);
        } else {
            merged.add(cur);
        }
    }
    return merged.toArray(new int[0][]);
}

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    for cur in intervals:
        if merged and cur[0] <= merged[-1][1]:
            # 有重叠，扩展右端点；注意 cur 可能被完全包住
            merged[-1][1] = max(merged[-1][1], cur[1])
        else:
            merged.append(cur)
    return merged

func merge(intervals [][]int) [][]int {
    slices.SortFunc(intervals, func(a, b []int) int { return a[0] - b[0] })
    merged := [][]int{}
    for _, cur := range intervals {
        n := len(merged)
        if n > 0 && cur[0] <= merged[n-1][1] {
            // 有重叠，扩展右端点；注意 cur 可能被完全包住
            merged[n-1][1] = max(merged[n-1][1], cur[1])
        } else {
            merged = append(merged, cur)
        }
    }
    return merged
}

pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    intervals.sort_by_key(|iv| iv[0]);
    let mut merged: Vec<Vec<i32>> = Vec::new();
    for cur in intervals {
        match merged.last_mut() {
            // 有重叠，扩展右端点；注意 cur 可能被完全包住
            Some(last) if cur[0] <= last[1] => last[1] = last[1].max(cur[1]),
            _ => merged.push(cur),
        }
    }
    merged
}

最容易错的一行是 max(last[1], cur[1])。排序只按左端点，cur 的右端点未必更大——比如 [1,10] 后面跟着 [2,3]，若直接写 last[1] = cur[1]，区间会被错误地缩短。另外重叠判断用 <= 而不是 <：题目里 [1,4] 和 [4,5] 这种端点相触的算重叠，要并成 [1,5]。

复杂度

指标	复杂度	原因
时间	`O(n log n)`	排序占主导，之后线性扫描一遍
空间	`O(log n)`	排序的栈开销；结果集不算额外空间

可以迁移的模式

区间问题先按左端点（或右端点）排序，把二维的重叠关系降成线性扫描；
排序后维护一个“当前正在生长的区间”，新元素要么并入它、要么让它定稿；
合并时对两个端点分别取极值，别默认后来者的右端点更大。

“排序 + 与结果尾部比较”这套流程，在插入区间（57）、会议室（253）等区间题里都是同一副骨架。