学设计哪个职业学校比较好_网页链接制作软件_电脑培训网_网站开发的一般流程

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

示例 1：

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

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

提示：

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals 根据 starti 按 升序 排列
• newInterval.length == 2
• 0 <= start <= end <= 105

答案:

#define MAX_VAL(a, b) (a > b ? a : b)
#define MIN_VAL(a, b) (a < b ? a : b) // leecode 57.插入区间
int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes) {// 方案1： 将要插入的区间直接加到数组中，再给区间排序，再合并区间// 方案2： 因为给出的区间数组已经是升序的了，只需要将要插入的区间依次和数组中区间对比，有重合则合并区间， 无重复则在合适的时机插入新区间。// 使用方案2：*returnSize = 0; // 返回新的二维数组的长度，即区间个数，后面更新数组时动态修改其大小。 int** res = (int**)malloc(sizeof(int*) * (intervalsSize + 1)); // 最多需要这么大内存空间if (!res) {fprintf(stderr, "Failed to malloc!\n");exit(EXIT_FAILURE);}// returnColumnSizes 标识返回的二维数组中，每个一维数组的长度*returnColumnSizes = (int*)malloc(sizeof(int*) * (intervalsSize + 1)); // 最多需求这么多内存if (!(*returnColumnSizes)) {fprintf(stderr, "Failed to malloc!\n");exit(EXIT_FAILURE);}// 遍历数组，合并区间, 并在合适的时机插入区间int left = newInterval[0];int right = newInterval[1];bool insert = false; // 目标区间是否已插入for (int i = 0; i < intervalsSize; i++) {int* interval = *(intervals + i); // 或者这样写int* interval = intervals[i];if (insert) {// 目标区间已插入了，只需要加入原有区间int* interval_ = (int*)malloc(sizeof(int) * 2);if (!interval_) {fprintf(stderr, "Failed to malloc!\n");exit(EXIT_FAILURE);}memcpy(interval_, interval, sizeof(int) * 2);(*returnColumnSizes)[*returnSize] = 2; // returnColumnSizes标识返回的二维数组中，每个一维数组的长度，每个一维数组长度为2res[(*returnSize)++] = interval_;continue;}if (right < interval[0]) {// 不重合，此时不能合并区间，插入该区间insert = true;int* newInterval_ = (int*)malloc(sizeof(int) * 2);if (!newInterval_) {fprintf(stderr, "Failed to malloc!\n");exit(EXIT_FAILURE);}newInterval_[0] = left;newInterval_[1] = right;(*returnColumnSizes)[*returnSize] = 2;res[(*returnSize)++] = newInterval_;// 原区间还是要加入结果集。// 这里直接复制上面那一块代码了。int* interval_ = (int*)malloc(sizeof(int) * 2);if (!interval_) {fprintf(stderr, "Failed to malloc!\n");exit(EXIT_FAILURE);}memcpy(interval_, interval, sizeof(int) * 2);(*returnColumnSizes)[*returnSize] = 2; // returnColumnSizes标识返回的二维数组中，每个一维数组的长度，每个一维数组长度为2res[(*returnSize)++] = interval_;}else if (left > interval[1]) {// 不重合， 还不能插入，只需要加入原有区间int* interval_ = (int*)malloc(sizeof(int) * 2);if (!interval_) {fprintf(stderr, "Failed to malloc!\n");exit(EXIT_FAILURE);}memcpy(interval_, interval, sizeof(int) * 2);(*returnColumnSizes)[*returnSize] = 2; // returnColumnSizes标识返回的二维数组中，每个一维数组的长度，每个一维数组长度为2res[(*returnSize)++] = interval_;}else {// 区间有重合， 和当前区间合并为一个更大区间, 更新该区间范围left = MIN_VAL(interval[0], left);right = MAX_VAL(interval[1], right);}}// 最后还需判断是否插入了，未插入说明该区间应该插入到最后if (!insert) {int* newInterval_ = (int*)malloc(sizeof(int) * 2);if (!newInterval_) {fprintf(stderr, "Failed to malloc!\n");exit(EXIT_FAILURE);}newInterval_[0] = left;newInterval_[1] = right;(*returnColumnSizes)[*returnSize] = 2;res[(*returnSize)++] = newInterval_;}return res;
}

测试代码：

void testLeeCode57() {int arr1[] = {1, 3};int arr2[] = {6, 9};int* intervals[] = { arr1, arr2}; // intervals为int*数组，所以其类型则为int** int intervalsSize = sizeof(intervals) / sizeof(intervals[0]);int* intervalsColSize = (int*)malloc(sizeof(int) * intervalsSize);if (!intervalsColSize) {fprintf(stderr, "Failed to malloc!\n");exit(EXIT_FAILURE);}for (int i = 0; i < intervalsSize; i++) {intervalsColSize[i] = 2;}int newInterval[] = {2, 5};int newIntervalSize = 2;int returnSize;int* returnColumnSizes;int** res = insert(intervals, intervalsSize, intervalsColSize, newInterval, newIntervalSize, &returnSize, &returnColumnSizes);// 打印结果printf("[");for (int i = 0; i < returnSize; i++) {printf("[%d, %d]", res[i][0], res[i][1]);if (i != returnSize - 1) {printf(",");}}printf("]");// 释放内存free(returnColumnSizes);free(intervalsColSize);// 必须先释放每一行的内存for (int i = 0; i < returnSize; i++) {free(res[i]);}// 再释放行指针数组free(res);
}

测试打印结果：

ok！