力扣第57题：插入区间问题（C语言）

问题描述

力扣第57题 插入区间 要求我们将一个新的区间插入到一个非重叠且有序的区间列表中，并合并可能重叠的区间。

题目要求

给定一组区间和一个新区间：

插入新区间，保持区间列表的非重叠性和有序性。
合并与新区间重叠的部分，输出最终结果。

例如：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

解决思路

观察区间关系：
- 如果区间在新区间左侧：可以直接加入结果。
- 如果区间与新区间重叠：需要调整新区间的左右边界，直到不重叠为止。
- 如果区间在新区间右侧：在遇到第一个右侧区间时，可以直接将新区间加入结果，随后把剩余的区间加入结果。
动态内存分配：
- 由于题目需要返回一个新的二维数组，我们需要通过动态内存管理来分配内存。

代码实现

#include <stdio.h>
#include <stdlib.h>// Helper function to get the minimum of two values
int min(int a, int b) {return a < b ? a : b;
}// Helper function to get the maximum of two values
int max(int a, int b) {return a > b ? a : b;
}// Main function to insert and merge intervals
int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes) {// Allocate space for the resultint** result = (int**)malloc((intervalsSize + 1) * sizeof(int*));*returnColumnSizes = (int*)malloc((intervalsSize + 1) * sizeof(int));int idx = 0; // Index to track result arrayint i = 0;// Step 1: Add all intervals that end before the new interval startswhile (i < intervalsSize && intervals[i][1] < newInterval[0]) {result[idx] = (int*)malloc(2 * sizeof(int));result[idx][0] = intervals[i][0];result[idx][1] = intervals[i][1];(*returnColumnSizes)[idx] = 2;idx++;i++;}// Step 2: Merge all overlapping intervals with the new intervalwhile (i < intervalsSize && intervals[i][0] <= newInterval[1]) {newInterval[0] = min(newInterval[0], intervals[i][0]);newInterval[1] = max(newInterval[1], intervals[i][1]);i++;}// Add the merged intervalresult[idx] = (int*)malloc(2 * sizeof(int));result[idx][0] = newInterval[0];result[idx][1] = newInterval[1];(*returnColumnSizes)[idx] = 2;idx++;// Step 3: Add all remaining intervalswhile (i < intervalsSize) {result[idx] = (int*)malloc(2 * sizeof(int));result[idx][0] = intervals[i][0];result[idx][1] = intervals[i][1];(*returnColumnSizes)[idx] = 2;idx++;i++;}// Update the return size*returnSize = idx;return result;
}

示例测试代码

int main() {// Input intervalsint intervalsSize = 2;int intervalsColSize[] = {2, 2};int** intervals = (int**)malloc(intervalsSize * sizeof(int*));intervals[0] = (int*)malloc(2 * sizeof(int));intervals[0][0] = 1; intervals[0][1] = 3;intervals[1] = (int*)malloc(2 * sizeof(int));intervals[1][0] = 6; intervals[1][1] = 9;// New intervalint newInterval[] = {2, 5};int newIntervalSize = 2;// Output variablesint returnSize;int* returnColumnSizes;// Call the insert functionint** result = insert(intervals, intervalsSize, intervalsColSize, newInterval, newIntervalSize, &returnSize, &returnColumnSizes);// Print the resultprintf("Merged Intervals:\n");for (int i = 0; i < returnSize; i++) {printf("[%d, %d] ", result[i][0], result[i][1]);free(result[i]);}printf("\n");// Free allocated memoryfree(result);free(returnColumnSizes);for (int i = 0; i < intervalsSize; i++) {free(intervals[i]);}free(intervals);return 0;
}

运行结果

输入：

intervals = [[1,3],[6,9]], newInterval = [2,5]

输出：

Merged Intervals:
[1, 5] [6, 9]

代码解析

输入参数：
- intervals：二维数组表示区间列表。
- newInterval：待插入的区间。
步骤拆解：
- Step 1：将新区间左侧的所有区间直接加入结果。
- Step 2：合并与新区间重叠的所有区间。
- Step 3：将新区间右侧的所有区间直接加入结果。
内存管理：
- 使用 malloc 分配内存给结果数组和列大小数组。
- 在主函数中释放所有动态分配的内存，避免内存泄漏。