carloscn
commented
1 year ago 问题分析
先对数组进行排序，排序规则是按照左值进行排序，如果左值一致，按照右值排序。排序后的vec假如是sorted_vec.
制作一个函数，返回vec，输入两个vec list，对两个vec进行合并的算法。
准备一个空vec，遍历所有的sorted_vec，合并后的push到空vec中。
static int32_t merge_two_element(BUFFER_T *a_buf,
BUFFER_T *b_buf,
BUFLIST_T **out)
{
int32_t ret = 0;
int64_t a_l = 0, a_r = 0;
int64_t b_l = 0, b_r = 0;
UTILS_CHECK_PTR(out);
if (NULL == a_buf && NULL == b_buf) {
ret = -1;
goto finish;
}
*out = buflist_malloc();
UTILS_CHECK_PTR(*out);
if (NULL == a_buf && NULL != b_buf) {
if (buffer_get_current_len(b_buf) != 2) {
LOG("the b_buf len is not 2!\n");
ret = -1;
} else {
ret = buflist_add(*out, b_buf);
}
goto finish;
}
if (NULL != a_buf && NULL == b_buf) {
if (buffer_get_current_len(a_buf) != 2) {
ret = -1;
LOG("the a_buf len is not 2!\n");
} else {
ret = buflist_add(*out, a_buf);
}
goto finish;
}
if (buffer_get_current_len(a_buf) != 2 ||
buffer_get_current_len(b_buf) != 2) {
ret = -1;
LOG("the buf len is not 2 != %zu!\n", buffer_get_current_len(a_buf));
goto finish;
}
ret = buffer_get_by_index(a_buf, 0, &a_l);
UTILS_CHECK_RET(ret);
ret = buffer_get_by_index(a_buf, 1, &a_r);
UTILS_CHECK_RET(ret);
ret = buffer_get_by_index(b_buf, 0, &b_l);
UTILS_CHECK_RET(ret);
ret = buffer_get_by_index(b_buf, 1, &b_r);
UTILS_CHECK_RET(ret);
// a is []
// b is {}
// case1 : [ { } ] -> []
// case2 : { [ ] } -> {}
// case3 : { [ } ] -> {]
// case4 : [ { ] } -> [}
// case5 : { } [ ] -> {}, []
// case{6 : [ ] { } -> [], {}
// a_l = [
// a_r = ]
// b_l = {
// b_r = }
// case1 : [ { } ] -> []
if (b_l >= a_l && b_r <= a_r) {
int64_t buffer[2] = {a_l, a_r};
ret = buflist_append_array(*out, buffer, 2);
UTILS_CHECK_RET(ret);
// case2 : { [ ] } -> {}
} else if (a_l >= b_l && a_r <= b_r) {
int64_t buffer[2] = {b_l, b_r};
ret = buflist_append_array(*out, buffer, 2);
UTILS_CHECK_RET(ret);
// case3 : { [ } ] -> {]
} else if (a_l <= b_r && a_l >= b_l && b_r <= a_r) {
int64_t buffer[2] = {b_l, a_r};
ret = buflist_append_array(*out, buffer, 2);
UTILS_CHECK_RET(ret);
// case4 : [ { ] } -> [}
} else if (b_l >= a_l && b_l <= a_r && a_r <= b_r) {
int64_t buffer[2] = {a_l, b_r};
ret = buflist_append_array(*out, buffer, 2);
UTILS_CHECK_RET(ret);
// case5 : { } [ ] -> {}, []
} else if (b_r < a_l) {
int64_t buffer[2] = {b_l, b_r};
ret = buflist_append_array(*out, buffer, 2);
UTILS_CHECK_RET(ret);
buffer[0] = a_l, buffer[1] = a_r;
ret = buflist_append_array(*out, buffer, 2);
UTILS_CHECK_RET(ret);
// case6 : [ ] { } -> [], {}
} else if (a_r < b_l) {
int64_t buffer[2] = {a_l, a_r};
ret = buflist_append_array(*out, buffer, 2);
UTILS_CHECK_RET(ret);
buffer[0] = b_l, buffer[1] = b_r;
ret = buflist_append_array(*out, buffer, 2);
UTILS_CHECK_RET(ret);
}
finish:
return ret;
}
static int32_t merge_intervals(BUFLIST_T* b_list, BUFLIST_T *out_list)
{
int32_t ret = 0;
size_t i = 0;
size_t len = 0;
BUFFER_T *a = NULL;
BUFFER_T *b = NULL;
BUFLIST_T *ret_list = NULL;
UTILS_CHECK_PTR(b_list);
UTILS_CHECK_PTR(out_list);
UTILS_CHECK_LEN(len = buflist_get_size(b_list));
for (i = 0; i < len; i ++) {
BUFLIST_T *temp_list = NULL;
b = buflist_get_buffer_at(b_list, i);
UTILS_CHECK_PTR(b);
ret = merge_two_element(a, b, &temp_list);
UTILS_CHECK_RET(ret);
LOG("the i is %zu, and the merged is ", i);
buflist_infolog(temp_list);
buffer_free(a), a = NULL;
if (buflist_get_size(temp_list) == 2) {
ret = buflist_add(out_list, buflist_get_buffer_at(temp_list, 0));
UTILS_CHECK_RET(ret);
a = buflist_get_buffer_dup_at(temp_list, 1);
UTILS_CHECK_PTR(a);
} else if (buflist_get_size(temp_list) == 1) {
a = buflist_get_buffer_dup_at(temp_list, 0);
UTILS_CHECK_PTR(a);
} else {
LOG("error branch!\n");
while(1);
}
buflist_free(temp_list);
}
ret = buflist_add(out_list, a);
UTILS_CHECK_RET(ret);
finish:
buffer_free(a);
return ret;
}
问题描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti <= endi <= 104
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/merge-intervals