题解 | 合并区间

/**
 * struct Interval {
 *    int start;
 *    int end;
 *    Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        // 特殊情况处理：空数组或只有一个区间
        if (intervals.empty()) return {};
        if (intervals.size() == 1) return intervals;
        
        // 1. 按区间起点进行排序
        sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        });
        
        vector<Interval> result;
        
        // 2. 遍历区间，合并重叠区间
        for (const auto& interval : intervals) {
            // 如果结果为空，或者当前区间与上一个区间不重叠
            if (result.empty() || interval.start > result.back().end) {
                result.push_back(interval);
            } else {
                // 合并区间：更新上一个区间的结束位置
                result.back().end = max(result.back().end, interval.end);
            }
        }
        
        return result;
    }
};

算法思路：

1. 排序：首先将所有区间按照起点进行升序排序
2. 合并：遍历排序后的区间：如果当前区间与结果中的最后一个区间不重叠（当前区间的起点 > 最后一个区间的终点），直接将当前区间加入结果如果重叠，更新最后一个区间的终点为两者终点的最大值

排序的数学原理

排序后，对于任意三个区间 A, B, C（A.start ≤ B.start ≤ C.start）：

3. 如果 A 与 C 重叠，那么 B 一定也与 C 重叠（因为 B.start ≤ C.start ≤ A.end）
4. 这意味着我们只需要维护一个"当前合并区间"，而不需要维护多个可能重叠的区间