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

时间：2024-11-20 19:32:37

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

问题描述

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

题目要求

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

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

例如：

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

解决思路

  1. 观察区间关系：

    • 如果区间在新区间左侧：可以直接加入结果。
    • 如果区间与新区间重叠：需要调整新区间的左右边界，直到不重叠为止。
    • 如果区间在新区间右侧：在遇到第一个右侧区间时，可以直接将新区间加入结果，随后把剩余的区间加入结果。

  2. 动态内存分配：

    • 由于题目需要返回一个新的二维数组，我们需要通过动态内存管理来分配内存。

代码实现 

#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 result
    int** result = (int**)malloc((intervalsSize + 1) * sizeof(int*));
    *returnColumnSizes = (int*)malloc((intervalsSize + 1) * sizeof(int));
    int idx = 0; // Index to track result array

    int i = 0;

    // Step 1: Add all intervals that end before the new interval starts
    while (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 interval
    while (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 interval
    result[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 intervals
    while (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 intervals
    int 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 interval
    int newInterval[] = {2, 5};
    int newIntervalSize = 2;

    // Output variables
    int returnSize;
    int* returnColumnSizes;

    // Call the insert function
    int** result = insert(intervals, intervalsSize, intervalsColSize, 
                          newInterval, newIntervalSize, 
                          &returnSize, &returnColumnSizes);

    // Print the result
    printf("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 memory
    free(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]

代码解析

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

时间复杂度分析

  • 时间复杂度：O(n)，因为只遍历了所有区间一次。
  • 空间复杂度：O(n)，由于存储了新的结果数组。

相关文章