LeetCode Hot 100 | 14. 合并数组

LeetCode 56. 合并区间 (Merge Intervals)

1. 核心解题思路：排序与贪心

为什么选择按"左端点"排序？ 将区间按 左端点 (Start Time) 从小到大排序是解题的关键。

• 直观理解：排序后，所有区间在数轴上是"紧凑排列"的。如果我们把区间看作线段，按左端点排序能让它们尽可能地"靠左"聚集。

• 数学意义：当按左端点排序后，对于任意两个相邻区间 A 和 B（A 在 B 前），我们只需要关注 A 的右端点是否覆盖了 B 的左端点。

  • 如果覆盖（Overlap），说明可以合并，且不需要回头看之前的区间。

  • 如果未覆盖，说明 A 已经独立，可以直接存入结果集。

对比思考：如果按右端点排序，虽然右边对齐了，但左边可能参差不齐（比如一个很长的区间 [1,100] 可能包含了很多短区间），导致我们很难通过一次线性扫描完成合并。

---

2. C++ STL 深度优化：Sort 与 Functor

关于 sort 自定义比较器的点非常专业，这是 C++ 高性能编程的一个重要细节。

• Functor (仿函数) vs. 函数指针： 在 std::sort 中，传入一个重载了 operator() 的类（Functor）通常比传入裸函数指针效率更高。

• 原理：

  • Functor：编译器在编译期就能确定类型，因此可以将比较逻辑（operator()）直接内联 (Inline) 到排序算法的循环内部，消除了函数调用的开销。

  • 函数指针：编译器通常无法在编译期预测指针指向哪个函数，因此很难进行内联优化，导致每次比较都产生一次间接函数调用。

代码演进： 除了传统的 struct 写法，现代 C++ (C++11及以后) 更推荐使用 Lambda 表达式，它本质上是编译器自动生成的匿名 Functor，既保留了内联的高效，又让代码更简洁。

---

3. 代码实现 (优化版)

保留了逻辑框架，微调了 emplace_back 的写法以利用 C++ 的构造特性，并添加了必要的注释。

class Solution {
private:
    // 方式一：传统的仿函数 (Functor)
    // 优势：类型安全，极易被编译器内联优化
    struct IntervalComparator {
        bool operator()(const vector<int>& a, const vector<int>& b) const {
            return a[0] < b[0];
        }
    };

public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};

        // 1. 排序：将所有区间按左端点升序排列
        // 这里也可以用 Lambda: sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) { return a[0] < b[0]; });
        sort(intervals.begin(), intervals.end(), IntervalComparator());

        vector<vector<int>> result;
        
        // 初始化当前的合并区间
        int currentLeft = intervals[0][0];
        int currentRight = intervals[0][1];

        // 2. 线性扫描
        // 优化：从 i=1 开始遍历即可，因为 i=0 已经在上面初始化过了
        for (int i = 1; i < intervals.size(); i++) {
            // 情况 A: 重叠 (当前区间的左端点 <= 维护区间的右端点)
            if (intervals[i][0] <= currentRight) {
                // 合并：右边界延伸到两者的最大值
                currentRight = max(currentRight, intervals[i][1]);
            } 
            // 情况 B: 不重叠 (出现断层)
            else {
                // 将旧的区间推入结果集
                result.push_back({currentLeft, currentRight});
                // 开启一个新的维护区间
                currentLeft = intervals[i][0];
                currentRight = intervals[i][1];
            }
        }

        // 3. 收尾 (易错点)
        // 循环结束后，最后一个被维护的区间还没有被推入结果集，需要手动处理
        result.push_back({currentLeft, currentRight});

        return result;
    }
};

---

4. 关键点备忘

1. 时序问题 (The "Final Push")： 在循环中，我们总是在发现"不重叠"时才把上一个区间存入结果。这意味着最后一个区间永远不会在循环内触发"存入"操作，必须在循环外单独 push_back 一次。

2. 贪心策略： 合并后的右边界取决于 max(currentRight, nextRight)。必须取最大值，因为有可能出现"大区间包小区间"的情况（例如 [1, 10] 和 [2, 3]，合并后应维持 10 而不是 3）。

3. 引用传参： 自定义比较器中的参数建议使用 const vector<int>&，避免拷贝大量 vector 数据，提升性能。