56. 合并区间（Merge Intervals）——C语言高质量题解

题目描述

给你一个区间集合intervals，其中每个区间为[start, end]，请合并所有重叠区间，并返回一个不重叠的区间数组，覆盖所有输入区间。

示例

示例 1：

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

示例 2：

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

解题思路

1️⃣ 排序

先按区间起点升序排序：

• 保证遍历时，所有可能重叠的区间是连续的

2️⃣ 遍历合并

维护当前区间[start, end]：

• 不重叠：保存当前区间 → 更新为新区间

• 重叠：更新end = max(end, intervals[i][1])

3️⃣ 最后一个区间

循环结束后，记得把最后的[start, end]加入结果。

图解

假设输入：

[[1,3],[2,6],[8,10],[15,18]]

1. 排序后：

[[1,3],[2,6],[8,10],[15,18]]

1. 合并[1,3]和[2,6]→[1,6]

2. [8,10]不重叠 → 直接加入

3. [15,18]不重叠 → 直接加入

最终结果：

[[1,6],[8,10],[15,18]]

C语言实现

#include <stdlib.h> // 排序函数：按区间起点升序 int cmp(const void* a, const void* b) { int* p1 = *(int**)a; int* p2 = *(int**)b; return p1[0] - p2[0]; } int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) { if (intervalsSize == 0) { *returnSize = 0; return NULL; } qsort(intervals, intervalsSize, sizeof(int*), cmp); int** res = (int**)malloc(sizeof(int*) * intervalsSize); *returnColumnSizes = (int*)malloc(sizeof(int) * intervalsSize); int count = 0; int start = intervals[0][0]; int end = intervals[0][1]; for (int i = 1; i < intervalsSize; i++) { if (intervals[i][0] > end) { res[count] = (int*)malloc(sizeof(int) * 2); res[count][0] = start; res[count][1] = end; (*returnColumnSizes)[count] = 2; count++; start = intervals[i][0]; end = intervals[i][1]; } else { if (intervals[i][1] > end) end = intervals[i][1]; } } // 加入最后一个区间 res[count] = (int*)malloc(sizeof(int) * 2); res[count][0] = start; res[count][1] = end; (*returnColumnSizes)[count] = 2; count++; *returnSize = count; return res; }

易错点

1. 没有排序

   • 若不排序，合并逻辑会失败

2. 忘记最后一个区间

   • 循环结束后必须手动加入

3. malloc/returnColumnSizes

   • LeetCode 题要求返回的数组必须 malloc

4. 重叠条件

   • 注意intervals[i][0] <= end才算重叠

时间复杂度

• 排序：O(n log n)

• 遍历合并：O(n)

• 总计：O(n log n)

空间复杂度

• 返回数组：O(n)

• 排序原数组如果用 qsort 可以原地排序，额外空间O(log n)（qsort递归栈）

✅总结

1. 排序保证顺序

2. 遍历 + 贪心合并

3. 注意内存分配与返回格式