代码实现:
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ // 交换 void swap(int *m, int *n) { int temp = *m; *m = *n; *n = temp; } // 快排 void sort(int **nums, int l, int r) { // 左闭右开 if (r - l <= 2) { if (r - l <= 1) { // 剩余个数:<= 1 return; } if (nums[r - 1][0] < nums[l][0]) { // 剩余个数:= 2 且后者小于前者 交换 swap(&nums[r - 1][0], &nums[l][0]); swap(&nums[r - 1][1], &nums[l][1]); } return; } int x = nums[l][0]; int y = nums[l][1]; int i = l, j = r - 1; while (i < j) { while (i < j && nums[j][0] >= x) { j--; } if (i < j) { nums[i][0] = nums[j][0]; nums[i][1] = nums[j][1]; i++; } while (i < j && nums[i][0] <= x) { i++; } if (i < j) { nums[j][0] = nums[i][0]; nums[j][1] = nums[i][1]; j--; } } nums[i][0] = x, nums[i][1] = y; sort(nums, l, i); sort(nums, i + 1, r); } int** merge(int **intervals, int intervalsSize, int *intervalsColSize, int *returnSize, int **returnColumnSizes){ if (intervalsSize == 0) { return NULL; } *returnSize = 0; // 按左边界(从小到大)快排 sort(intervals, 0, intervalsSize); // 左闭右开 *returnColumnSizes = malloc(sizeof(int) * intervalsSize); int **res = malloc(sizeof(int*) * intervalsSize); // 记录结果 int left = intervals[0][0]; int right = intervals[0][1]; for (int i = 1; i < intervalsSize; i++) { if (right >= intervals[i][0]) { right = right > intervals[i][1] ? right : intervals[i][1]; } else { (*returnColumnSizes)[(*returnSize)] = 2; res[(*returnSize)] = malloc(sizeof(int) * 2); res[(*returnSize)][0] = left; res[(*returnSize)][1] = right; (*returnSize)++; left = intervals[i][0]; right = intervals[i][1]; } } // 记录合并的最后一个区间 (*returnColumnSizes)[(*returnSize)] = 2; res[(*returnSize)] = malloc(sizeof(int) * 2); res[(*returnSize)][0] = left; res[(*returnSize)][1] = right; (*returnSize)++; return res; }