LeetCode 56. 合并区间

◎

本节目标

按左端点排序后，只与已合并结果的末区间比较并扩展边界。

这道题承接数组与区间：排序把可能相交的区间放到相邻位置，使扫描时只需关注结果末尾。

查看原题

题意与约束

合并所有重叠区间并返回不重叠结果。端点相接的区间也应合并。

朴素思路及瓶颈

可以反复扫描所有区间对，发现重叠就合并，再从头寻找新的重叠关系。一次完整扫描要比较 O(n²) 对区间，而一次合并又可能触发下一轮扫描，最坏时间复杂度可达 O(n³)。先按左端点排序后，可能与当前区间重叠的候选会集中在已合并结果的末尾，便能用一次线性扫描完成合并。

排序后的末尾不变量

按左端点排序后，结果列表中的区间已经完成合并。当前区间左端点若不超过结果末尾的右端点，就与末尾重叠，扩展右端点；否则它不可能与更早区间重叠，可以直接追加。

代码实现

两份源码处理空输入后排序，并维护已合并结果的最后一个区间。

C++

C++17

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> answer{intervals[0]};
        for (size_t index = 1; index < intervals.size(); index++) {
            if (intervals[index][0] <= answer.back()[1]) {
                answer.back()[1] = max(answer.back()[1], intervals[index][1]);
            } else {
                answer.push_back(intervals[index]);
            }
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        if not intervals:
            return []
        intervals.sort()
        answer = [intervals[0]]
        for left, right in intervals[1:]:
            if left <= answer[-1][1]:
                answer[-1][1] = max(answer[-1][1], right)
            else:
                answer.append([left, right])
        return answer

复杂度分析

排序占 O(n log n) 时间，扫描为 O(n)；除返回结果外，排序空间由语言实现决定。

易错点

• 使用严格小于，漏合并端点相接的区间。
• 扩展时直接覆盖右端点，反而把更大的边界缩小。

模式迁移

一组对象按关键字段排序后，如果当前对象只可能影响结果末尾，通常可以用一次扫描维护局部不变量；区间调度和扫描线问题也常从这里开始。