leetcode做题笔记57

给你一个 无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

思路一:模拟题意

int pushbackInterval(int **result, int num, int *element, int *colSize) {
    result[num] = (int*)malloc(sizeof(int)*10);
    result[num][0] = element[0];
    result[num][1] = element[1];
    colSize[num] = 2;
    return num + 1;
}

int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes){
    int *insert = newInterval;
    int **result = (int**)malloc(sizeof(int*)*(intervalsSize+1));
    *returnColumnSizes = (int*)malloc(sizeof(int)*(intervalsSize+1));
    
    int num = 0;
    for (int i = 0; i < intervalsSize; i++) {
        int *e = intervals[i];
        
        if (!insert) {
            num = pushbackInterval(result, num, e, *returnColumnSizes);
            continue;
        }
        
        if (e[1] < insert[0]) {
            num = pushbackInterval(result, num, e, *returnColumnSizes);
            continue;
        }
        
        if (e[0] > insert[1]) {
            num = pushbackInterval(result, num, insert, *returnColumnSizes);
            insert = NULL;
            
            num = pushbackInterval(result, num, e, *returnColumnSizes);
            continue;
        }
        
        insert[0] = insert[0] < e[0] ? insert[0] : e[0];
        insert[1] = insert[1] > e[1] ? insert[1] : e[1];
    }
    
    if (insert) {
        num = pushbackInterval(result, num, insert, *returnColumnSizes);
    }
    
    *returnSize = num;
    return result;
}

分析:

本题与上题很像,可将新的数组加入原数组中采用上一题的代码即可做出,同时也可以编写一个函数来使两个重叠的数组合并,result[num][0] = element[0];result[num][1] = element[1];colSize[num] = 2;return num + 1;便可将数组赋为正确值,最后输出即可

总结:

本题考察对数组的应用,将新增的数组与原二维数组合并可解决问题