【掌握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題的無堆疊區間合併功能。