力扣LCR074题：5分钟掌握高效合并重叠区间的技巧

一、问题理解

力扣LCR074题要求我们合并所有重叠的区间。给定一个区间集合，其中每个区间表示为[start, end]，我们需要合并所有有重叠的区间，最终返回一个不重叠的区间数组，且这个数组需要恰好覆盖输入中的所有区间。

例如：
输入：[[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠，合并为 [1,6]

二、解决思路

解决这个问题的主要步骤是：

1. ‌排序‌：首先将所有区间按照起始点进行排序

2. ‌合并‌：然后遍历排序后的区间，逐个合并重叠的区间

三、C++代码实现

C++

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
    
    // 1. 按照区间起始点排序
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);
    
    // 2. 遍历并合并重叠区间
    for (int i = 1; i < intervals.size(); ++i) {
        // 获取最后一个合并后的区间
        vector<int>& last = merged.back();
        
        // 如果当前区间与最后一个合并区间重叠
        if (intervals[i][0] <= last[1]) {
            // 合并区间，取最大的结束点
            last[1] = max(last[1], intervals[i][1]);
        } else {
            // 不重叠，直接添加新区间
            merged.push_back(intervals[i]);
        }
    }
    
    return merged;
    }
};

四、代码详解

1. ‌排序阶段‌：

• 使用标准库的sort函数，按照区间的起始点进行升序排序

• 自定义比较函数确保我们只比较区间的起始点

2. ‌合并阶段‌：

• 初始化merged数组，放入第一个区间

• 遍历后续区间，每次比较当前区间与merged中最后一个区间

• 如果重叠（当前区间的起始点 <= 最后一个区间的结束点），则合并

• 否则，将当前区间添加到merged中

五、常见问题解答

‌Q1: 为什么要先排序？‌
A: 排序后可以确保所有区间按起始点有序排列，这样我们只需要比较当前区间与最后一个合并区间即可，大大简化了合并逻辑。

‌Q2: 如何处理空输入？‌
A: 代码开头有检查，如果输入为空，直接返回空数组。

‌Q3: 如何判断两个区间是否重叠？‌
A: 如果区间A的起始点 <= 区间B的结束点，且区间B的起始点 <= 区间A的结束点，则它们重叠。但在排序后，我们只需要检查当前区间的起始点是否 <= 最后一个合并区间的结束点。

六、扩展思考

1. 如果区间包含浮点数而非整数，算法是否仍然适用？

2. 如何修改算法以处理半开区间（如[1,5)）？

3. 如果需要统计合并后每个区间被原始区间覆盖的次数，该如何实现？

希望这篇文章能帮助你理解区间合并算法的核心思想与实现细节！

来源：力扣LCR074题：5分钟掌握高效合并重叠区间的技巧