From 3164a692e8f47404f9a50f0e09a4bfe16351f15d Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sat, 15 Feb 2025 20:48:43 -0700 Subject: 56. merge intervals --- merge_intervals.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) create mode 100644 merge_intervals.c (limited to 'merge_intervals.c') 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); +} -- cgit v1.2.3