aboutsummaryrefslogtreecommitdiff
path: root/merge_intervals.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-15 20:48:43 -0700
committerJack Sangdahl <[email protected]>2025-02-15 20:48:43 -0700
commit3164a692e8f47404f9a50f0e09a4bfe16351f15d (patch)
treeec5e4be69bee3df426dac4b1a043c2df6f9cbb4b /merge_intervals.c
parentc217c4688d9bcfba1685f27658c7c036bbccabf5 (diff)
downloadleetcode-3164a692e8f47404f9a50f0e09a4bfe16351f15d.tar.gz
leetcode-3164a692e8f47404f9a50f0e09a4bfe16351f15d.zip
56. merge intervals
Diffstat (limited to 'merge_intervals.c')
-rw-r--r--merge_intervals.c63
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);
+}