【掌握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题的无堆叠区间兼并功能。