力扣面试经典——56题

💡 参考代码：

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于按区间起始位置排序
int compare(const void *a, const void *b) {
    int *intervalA = *(int **)a;
    int *intervalB = *(int **)b;
    return intervalA[0] - intervalB[0];
}

/**
 * 合并重叠区间
 * @param intervals 输入的区间数组
 * @param intervalsSize 区间数组长度
 * @param intervalsColSize 每个区间元素的列数（通常为2）
 * @param returnSize 返回数组的行数
 * @param returnColumnSizes 返回数组每行的列数
 * @return 合并后的区间数组
 */
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
    // 特殊情况处理：如果输入为空，直接返回
    if (intervalsSize == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    // 按照区间起始位置对输入数组进行排序
    qsort(intervals, intervalsSize, sizeof(int*), compare);
    
    // 分配结果数组内存空间
    int **result = (int**)malloc(sizeof(int*) * intervalsSize);
    *returnColumnSizes = (int*)malloc(sizeof(int) * intervalsSize);
    
    // 初始化第一个区间为结果数组的第一个元素
    result[0] = (int*)malloc(sizeof(int) * 2);
    result[0][0] = intervals[0][0];
    result[0][1] = intervals[0][1];
    (*returnColumnSizes)[0] = 2;
    
    // 记录结果数组当前元素个数
    int count = 1;
    
    // 遍历排序后的区间数组
    for (int i = 1; i < intervalsSize; i++) {
        // 如果当前区间与前一个区间重叠（当前区间起始 <= 前一个区间结束）
        if (intervals[i][0] <= result[count - 1][1]) {
            // 合并区间：更新结束位置为两个区间结束位置的最大值
            result[count - 1][1] = fmax(result[count - 1][1], intervals[i][1]);
        } else {
            // 如果不重叠，将当前区间加入结果数组
            result[count] = (int*)malloc(sizeof(int) * 2);
            result[count][0] = intervals[i][0];
            result[count][1] = intervals[i][1];
            (*returnColumnSizes)[count] = 2;
            count++;
        }
    }
    
    // 设置返回数组大小
    *returnSize = count;
    return result;
}

📖 总结：

点击展开题目总结

🤔 合并区间

---

1️⃣ 题目核心信息

🎯 功能描述：给定一个区间数组，合并所有重叠的区间，返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

📥 输入输出：

• 输入：intervals - 二维整数数组，表示多个区间；intervalsSize - 区间数量；intervalsColSize - 每个区间包含的元素个数
• 输出：合并后的不重叠区间数组，通过 returnSize 返回数组行数，通过 returnColumnSizes 返回每行列数

---

2️⃣ 实现原理

💡 核心思路：先按区间起始位置排序，然后遍历合并重叠区间。

📋 实现步骤：

1. 对输入的区间数组按起始位置进行排序
2. 初始化结果数组，将第一个区间加入结果
3. 遍历剩余区间，判断是否与结果数组中最后一个区间重叠
4. 如果重叠则合并，更新结束位置；否则将当前区间加入结果数组

---

3️⃣ 关键点解析

🎯 代码技巧

• 使用 qsort 对二维数组进行排序，自定义比较函数
• 通过比较当前区间起始位置与前一个区间结束位置判断是否重叠
• 合并时取两个区间结束位置的最大值作为新区间结束位置
• 动态管理内存分配和返回参数设置

4️⃣ 使用场景

✅ 适用情况：

• 时间区间合并
• 资源调度中的时间段整合
• 连续区间检测与合并

⚠️ 前提条件：

• 输入区间为有效的二维数组
• 每个区间包含起始和结束两个元素

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n log n)，主要消耗在排序上，其中 n 为区间数量
• 💾 空间复杂度：O(n)，用于存储结果数组

6️⃣ 注意事项

🚩 边界情况：

• 输入数组为空的情况
• 只有一个区间的情况
• 所有区间都不重叠的情况

💥 易错点：

• 忘记对区间进行排序导致合并错误
• 合并时未正确取最大结束位置
• 内存分配和返回参数设置错误

7️⃣ 补充说明

以示例1为例，逐步演示算法执行过程：

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]

第一步：排序

首先对区间数组按起始位置进行排序：

排序前: [[1,3],[2,6],[8,10],[15,18]]
排序后: [[1,3],[2,6],[8,10],[15,18]] (此例中已经有序)

第二步：初始化结果数组

将第一个区间 [1,3] 加入结果数组：

result = [[1,3]] count = 1

第三步：遍历并合并区间

处理区间 [2,6]:

比较 2 (当前区间起始) 与 3 (结果数组最后一个区间结束):

• 因为 2 <= 3，所以两个区间重叠
• 合并区间，更新结束位置为 max(3, 6) = 6

result = [[1,6]] count = 1

处理区间 [8,10]:

比较 8 (当前区间起始) 与 6 (结果数组最后一个区间结束):

• 因为 8 > 6，所以两个区间不重叠
• 将 [8,10] 添加到结果数组

result = [[1,6],[8,10]] count = 2

处理区间 [15,18]:

比较 15 (当前区间起始) 与 10 (结果数组最后一个区间结束):

• 因为 15 > 10，所以两个区间不重叠
• 将 [15,18] 添加到结果数组

result = [[1,6],[8,10],[15,18]] count = 3

第四步：返回结果

最终结果为: [[1,6],[8,10],[15,18]]

另一个例子：包含重叠边界的区间

输入: intervals = [[1,4],[4,5]]

排序后:

[[1,4],[4,5]]

处理过程:

1. 初始化: result = [[1,4]], count = 1

2. 处理 [4,5]:

   • 比较 4 与 4: 因为 4 <= 4，区间重叠
   • 合并区间，更新结束位置为 max(4, 5) = 5
   • 结果: result = [[1,5]], count = 1

3. 返回结果: [[1,5]]

这说明在区间问题中，一个区间的结束位置等于另一个区间的起始位置时，这两个区间也被视为重叠区间，需要合并。

加载评论中...