56. 合并区间

难度：🟡 Medium | 标签：排序、数组 | 状态：⬜ LeetCode 链接

思路

按起点排序。维护当前合并段 [curL, curR]，遇到新区间：

• 起点 ≤ curR：合并，curR = max(curR, end)
• 否则：把当前段推入答案，开新段

代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& a) {
        sort(a.begin(), a.end());
        vector<vector<int>> res;
        for (auto& it : a) {
            if (!res.empty() && it[0] <= res.back()[1]) {
                res.back()[1] = max(res.back()[1], it[1]);
            } else {
                res.push_back(it);
            }
        }
        return res;
    }
};

复杂度

• 时间 O(n log n)，空间 O(log n)（排序）

易错 / 回顾

• 排序后才能贪心合并
• 判合并是 <= 不是 <（[1,4] 和 [4,5] 要合并）
• res.back() 直接改而不是 pop + push，省一次拷贝