1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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);
}
|