diff options
author | Jack Sangdahl <[email protected]> | 2025-02-15 20:48:43 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-15 20:48:43 -0700 |
commit | 3164a692e8f47404f9a50f0e09a4bfe16351f15d (patch) | |
tree | ec5e4be69bee3df426dac4b1a043c2df6f9cbb4b /merge_intervals.c | |
parent | c217c4688d9bcfba1685f27658c7c036bbccabf5 (diff) | |
download | leetcode-3164a692e8f47404f9a50f0e09a4bfe16351f15d.tar.gz leetcode-3164a692e8f47404f9a50f0e09a4bfe16351f15d.zip |
56. merge intervals
Diffstat (limited to 'merge_intervals.c')
-rw-r--r-- | merge_intervals.c | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/merge_intervals.c b/merge_intervals.c new file mode 100644 index 0000000..d38a467 --- /dev/null +++ b/merge_intervals.c @@ -0,0 +1,63 @@ +// 56. Merge Intervals +#include "leetcode.h" + +/* + * given an array of 'intervals' where 'intervals[i] = [start_i, end_i]', merge + * all overlapping intervals, and return an array of the non-overlapping + * intervals that cover all the intervals in the input. + */ + +int cmp(const void *a, const void *b) { + return (*(int **)a)[0] - (*(int **)b)[0]; +} + +int **merge(int **intervals, int intervalsSize, int *intervalsColSize, + int *returnSize, int **returnColumnSizes) { + qsort(intervals, intervalsSize, sizeof(int *), cmp); + int **stack = (int **)malloc(intervalsSize * sizeof(int *)), top = 1; + stack[0] = intervals[0]; + for (int i = 1; i < intervalsSize; i++) { + if (intervals[i][0] <= stack[top - 1][1]) + stack[top - 1][1] = intervals[i][1] > stack[top - 1][1] + ? intervals[i][1] + : stack[top - 1][1]; + else + stack[top++] = intervals[i]; + } + *returnSize = top; + *returnColumnSizes = (int *)malloc((*returnSize) * sizeof(int)); + for (int i = 0; i < *returnSize; i++) + (*returnColumnSizes)[i] = 2; + return stack; +} + +int main() { + int i1i[4][2] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}}, + i2i[2][2] = {{1, 4}, {4, 5}}; + struct two_d_arr i1, i2; + two_d_arr_init(&i1, ARRAY_SIZE(i1i), ARRAY_SIZE(i1i[0]), i1i); + two_d_arr_init(&i2, ARRAY_SIZE(i2i), ARRAY_SIZE(i2i[0]), i2i); + int rs1, *rcs1, rs2, *rcs2; + int **m1 = merge(i1.arr, i1.row_size, i1.col_size, &rs1, &rcs1); + int **m2 = merge(i2.arr, i2.row_size, i2.col_size, &rs2, &rcs2); + for (int i = 0; i < rs1; i++) { + for (int j = 0; j < rcs1[i]; j++) + printf("%d ", m1[i][j]); // expect: [[1,6],[8,10],[15,18]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs2; i++) { + for (int j = 0; j < rcs2[i]; j++) + printf("%d ", m2[i][j]); // expect: [[1,5]] + printf("\n"); + } + printf("\n"); + for (int i = 0; i < rs1; i++) + free(m1[i]); + free(m1); + two_d_arr_free(&i1); + for (int i = 0; i < rs2; i++) + free(m2[i]); + free(m2); + two_d_arr_free(&i2); +} |