【掌握LeetCode 434题】C语言实现无重叠区间合并技巧

概述

LeetCode 434题“无重叠区间合并”要求我们将一组重叠的区间合并成无重叠的区间。在C语言中实现这一功能，我们需要遵循一定的算法步骤，通常涉及排序和区间合并的逻辑。

算法步骤

1. 排序区间

首先，我们需要根据区间的起始点对区间数组进行排序。如果两个区间的起始点相同，则可以根据结束点进行排序。

int compare(const void *a, const void *b) {
    int *intervals1 = *(int **)a;
    int *intervals2 = *(int **)b;
    if (intervals1[0] != intervals2[0])
        return intervals1[0] - intervals2[0];
    else
        return intervals1[1] - intervals2[1];
}

2. 合并区间

接着，我们使用一个循环遍历排序后的区间数组。对于当前区间和前一个区间，如果它们重叠，我们就合并它们。

int *merge(int **intervals, int intervalsSize) {
    if (intervalsSize == 0) return NULL;
    
    // 根据起始点排序区间
    qsort(intervals, intervalsSize, sizeof(int *), compare);
    
    int **result = malloc(sizeof(int *) * intervalsSize);
    int resultSize = 0;
    int *currentInterval = intervals[0];
    result[resultSize++] = currentInterval;
    
    for (int i = 1; i < intervalsSize; i++) {
        int *nextInterval = intervals[i];
        
        // 检查当前区间和下一个区间是否重叠
        if (currentInterval[1] >= nextInterval[0]) {
            // 合并区间
            currentInterval[1] = (currentInterval[1] > nextInterval[1]) ? currentInterval[1] : nextInterval[1];
        } else {
            // 不重叠，添加到结果中
            result[resultSize++] = nextInterval;
            currentInterval = nextInterval;
        }
    }
    
    // 重新分配结果数组的大小以匹配实际结果的大小
    result = realloc(result, sizeof(int *) * resultSize);
    return result;
}

3. 释放内存

最后，我们不要忘记释放我们动态分配的内存。

int main() {
    int **intervals = malloc(sizeof(int *) * 4);
    intervals[0] = malloc(sizeof(int) * 2);
    intervals[1] = malloc(sizeof(int) * 2);
    intervals[2] = malloc(sizeof(int) * 2);
    intervals[3] = malloc(sizeof(int) * 2);
    
    intervals[0][0] = 1; intervals[0][1] = 3;
    intervals[1][0] = 2; intervals[1][1] = 6;
    intervals[2][0] = 8; intervals[2][1] = 10;
    intervals[3][0] = 15; intervals[3][1] = 18;
    
    int *result = merge(intervals, 4);
    for (int i = 0; i < 3; i++) {
        printf("Interval %d: [%d, %d]\n", i + 1, result[i][0], result[i][1]);
        free(result[i]);
    }
    free(result);
    
    // 释放输入区间数组
    for (int i = 0; i < 4; i++) {
        free(intervals[i]);
    }
    free(intervals);
    
    return 0;
}

注意事项

• 确保排序和合并的逻辑正确无误。
• 在处理完所有区间后，释放分配的内存。
• 注意内存管理，防止内存泄漏。

通过以上步骤，我们可以在C语言中实现LeetCode 434题的无重叠区间合并功能。