diff options
-rw-r--r-- | merge_intervals.c | 63 | ||||
-rw-r--r-- | merge_intervals.py | 28 |
2 files changed, 91 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); +} diff --git a/merge_intervals.py b/merge_intervals.py new file mode 100644 index 0000000..74c64a6 --- /dev/null +++ b/merge_intervals.py @@ -0,0 +1,28 @@ +# 56. Merge Intervals + +""" +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. +""" + + +class Solution(object): + def merge(self, intervals): + """ + :type intervals: List[List[int]] + :rtype: List[List[int]] + """ + stack = [] + for i in sorted(intervals, key=lambda i: i[0]): + if stack and i[0] <= stack[-1][1]: + stack[-1][1] = max(stack[-1][1], i[1]) + else: + stack += [i] + return stack + + +if __name__ == "__main__": + obj = Solution() + print(obj.merge(intervals=[[1, 3], [2, 6], [8, 10], [15, 18]])) + print(obj.merge(intervals=[[1, 4], [4, 5]])) |