Skip to content

Commit 47ee065

Browse files
begeekmyfriendbegeekmyfriend
committed
Refine
Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>
1 parent 72fc910 commit 47ee065

File tree

2 files changed

+91
-225
lines changed

2 files changed

+91
-225
lines changed

‎056_merge_intervals/merge_intervals.c

Lines changed: 43 additions & 117 deletions
Original file line numberDiff line numberDiff line change
@@ -2,128 +2,52 @@
22
#include <stdlib.h>
33
#include <string.h>
44

5-
struct Interval {
6-
int start;
7-
int end;
8-
};
95

10-
static int binary_search(int *nums, int size, int target)
6+
static int compare(const void *a, const void *b)
117
{
12-
int low = -1;
13-
int high = size;
14-
while (low + 1 < high) {
15-
int mid = low + (high - low) / 2;
16-
if (target > nums[mid]) {
17-
low = mid;
18-
} else {
19-
high = mid;
20-
}
21-
}
22-
if (high == size || nums[high] != target) {
23-
return -high - 1;
24-
} else {
25-
return high;
26-
}
8+
return ((int *) a)[0] - ((int *) b)[0];
279
}
2810

2911
/**
30-
** Return an array of size *returnSize.
31-
** Note: The returned array must be malloced, assume caller calls free().
32-
**/
33-
static struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize)
12+
* Return an array of arrays of size *returnSize.
13+
* The sizes of the arrays are returned as *returnColumnSizes array.
14+
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
15+
*/
16+
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes)
3417
{
35-
struct Interval *p;
3618
if (intervalsSize == 0) {
37-
p = malloc(sizeof(*p));
38-
p->start = newInterval.start;
39-
p->end = newInterval.end;
40-
*returnSize = 1;
41-
return p;
19+
*returnSize = 0;
20+
return intervals;
4221
}
43-
44-
int i, count;
45-
int *nums = malloc(2 * intervalsSize * sizeof(int));
22+
23+
int i, len = 0;
24+
int *tmp = malloc(intervalsSize * 2 * sizeof(int));
4625
for (i = 0; i < intervalsSize; i++) {
47-
nums[i * 2] = intervals[i].start;
48-
nums[i * 2 + 1] = intervals[i].end;
49-
}
50-
51-
int start0 = binary_search(nums, 2 * intervalsSize, newInterval.start);
52-
int end0 = binary_search(nums, 2 * intervalsSize, newInterval.end);
53-
54-
int start1 = -1, end1 = -1;
55-
int merge_start= -1, merge_end = -1;
56-
if (start0 >= 0) {
57-
merge_start = start0 / 2;
58-
} else {
59-
start1 = -start0 - 1;
60-
merge_start = start1 / 2;
26+
tmp[i * 2] = intervals[i][0];
27+
tmp[i * 2 + 1] = intervals[i][1];
6128
}
29+
qsort(tmp, intervalsSize, 2 * sizeof(int), compare);
6230

63-
if (end0 >= 0) {
64-
merge_end = end0 / 2;
65-
} else {
66-
end1 = -end0 - 1;
67-
if (end1 % 2 == 0) {
68-
merge_end = end1 / 2 > 0 ? end1 / 2 - 1 : 0;
69-
} else {
70-
merge_end = end1 / 2;
31+
intervals[0][0] = tmp[0];
32+
intervals[0][1] = tmp[1];
33+
for (i = 1; i < intervalsSize; i++) {
34+
if (tmp[i * 2] > intervals[len][1]) {
35+
len++;
36+
intervals[len][0] = tmp[i * 2];
37+
intervals[len][1] = tmp[i * 2 + 1];
38+
} else if (tmp[i * 2 + 1] > intervals[len][1]) {
39+
intervals[len][1] = tmp[i * 2 + 1];
7140
}
7241
}
73-
74-
if (merge_start == merge_end) {
75-
if (start0 < 0 && end0 < 0 && start1 == end1 && start1 % 2 == 0) {
76-
count = intervalsSize + 1;
77-
p = malloc(count * sizeof(*p));
78-
memcpy(p, intervals, merge_start * sizeof(*p));
79-
p[merge_start] = newInterval;
80-
memcpy(p + merge_start + 1, intervals + merge_start, (intervalsSize - merge_start) * sizeof(*p));
81-
} else {
82-
count = intervalsSize;
83-
p = malloc(count * sizeof(*p));
84-
memcpy(p, intervals, count * sizeof(*p));
85-
if (start0 < 0 && start1 % 2 == 0) {
86-
p[merge_start].start = newInterval.start;
87-
}
88-
if (end0 < 0 && end1 % 2 == 0) {
89-
p[merge_end].end = newInterval.end;
90-
}
91-
}
92-
} else {
93-
count = intervalsSize - (merge_end - merge_start);
94-
p = malloc(count * sizeof(*p));
95-
memcpy(p, intervals, merge_start * sizeof(*p));
96-
memcpy(p + merge_start, intervals + merge_end, (intervalsSize - merge_end) * sizeof(*p));
97-
if (start0 < 0 && start1 % 2 == 0) {
98-
p[merge_start].start = newInterval.start;
99-
} else {
100-
p[merge_start].start = intervals[merge_start].start;
101-
}
102-
if (end0 < 0 && end1 % 2 == 0) {
103-
p[merge_start].end = newInterval.end;
104-
} else {
105-
p[merge_start].end = intervals[merge_end].end;
106-
}
42+
43+
len += 1;
44+
*returnSize = len;
45+
*returnColumnSizes = malloc(len * sizeof(int));
46+
for (i = 0; i < len; i++) {
47+
(*returnColumnSizes)[i] = 2;
10748
}
108-
109-
free(nums);
110-
free(intervals);
111-
*returnSize = count;
112-
return p;
113-
}
114-
115-
/**
116-
* * Return an array of size *returnSize.
117-
* * Note: The returned array must be malloced, assume caller calls free().
118-
* */
119-
struct Interval* merge(struct Interval* intervals, int intervalsSize, int* returnSize) {
120-
int i, count = 0;
121-
struct Interval *p = NULL;
122-
for (i = 0; i < intervalsSize; i++) {
123-
p = insert(p, count, intervals[i], &count);
124-
}
125-
*returnSize = count;
126-
return p;
49+
50+
return intervals;
12751
}
12852

12953
int main(int argc, char **argv)
@@ -134,18 +58,20 @@ int main(int argc, char **argv)
13458
}
13559

13660
int i, count = 0;
137-
struct Interval *intervals = malloc((argc - 1) / 2 * sizeof(struct Interval));
138-
struct Interval *p = intervals;
139-
for (i = 1; i < argc; i += 2) {
140-
p->start = atoi(argv[i]);
141-
p->end = atoi(argv[i + 1]);
142-
p++;
61+
int *sizes = malloc((argc - 1) / 2 * sizeof(int));
62+
int **intervals = malloc((argc - 1) / 2 * sizeof(int *));
63+
for (i = 0; i < (argc - 1) / 2; i++) {
64+
sizes[i] = 2;
65+
intervals[i] = malloc(2 * sizeof(int));
66+
intervals[i][0] = atoi(argv[i * 2 + 1]);
67+
intervals[i][1] = atoi(argv[i * 2 + 2]);
14368
}
14469

145-
struct Interval *q = merge(intervals, (argc - 1) / 2, &count);
70+
int *col_sizes;
71+
int **results = merge(intervals, (argc - 1) / 2, sizes, &count, &col_sizes);
14672
for (i = 0; i < count; i++) {
147-
printf("[%d, %d]\n", q->start, q->end);
148-
q++;
73+
printf("[%d,%d]\n", results[i][0], results[i][1]);
14974
}
75+
15076
return 0;
15177
}

‎057_insert_interval/insert_interval.c

Lines changed: 48 additions & 108 deletions
Original file line numberDiff line numberDiff line change
@@ -1,113 +1,52 @@
11
#include <stdio.h>
22
#include <stdlib.h>
3-
#include <string.h>
43

5-
struct Interval {
6-
int start;
7-
int end;
8-
};
94

10-
static int binary_search(int *nums, int size, int target)
5+
static int compare(const void *a, const void *b)
116
{
12-
int low = -1;
13-
int high = size;
14-
while (low + 1 < high) {
15-
int mid = low + (high - low) / 2;
16-
if (target > nums[mid]) {
17-
low = mid;
18-
} else {
19-
high = mid;
20-
}
21-
}
22-
if (high == size || nums[high] != target) {
23-
return -high - 1;
24-
} else {
25-
return high;
26-
}
7+
return ((int *) a)[0] - ((int *) b)[0];
278
}
289

2910
/**
30-
** Return an array of size *returnSize.
31-
** Note: The returned array must be malloced, assume caller calls free().
32-
**/
33-
static struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) {
34-
struct Interval *p;
35-
if (intervalsSize == 0) {
36-
p = malloc(sizeof(*p));
37-
p->start = newInterval.start;
38-
p->end = newInterval.end;
39-
*returnSize = 1;
40-
return p;
41-
}
42-
43-
int i, count;
44-
int *nums = malloc(2 * intervalsSize * sizeof(int));
11+
* Return an array of arrays of size *returnSize.
12+
* The sizes of the arrays are returned as *returnColumnSizes array.
13+
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
14+
*/
15+
int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes)
16+
{
17+
int i, len = 0;
18+
int *tmp = malloc((intervalsSize + 1) * 2 * sizeof(int));
4519
for (i = 0; i < intervalsSize; i++) {
46-
nums[i * 2] = intervals[i].start;
47-
nums[i * 2 + 1] = intervals[i].end;
20+
tmp[i * 2] = intervals[i][0];
21+
tmp[i * 2 + 1] = intervals[i][1];
4822
}
23+
tmp[i * 2] = newInterval[0];
24+
tmp[i * 2 + 1] = newInterval[1];
25+
qsort(tmp, intervalsSize + 1, 2 * sizeof(int), compare);
4926

50-
int start0 = binary_search(nums, 2 * intervalsSize, newInterval.start);
51-
int end0 = binary_search(nums, 2 * intervalsSize, newInterval.end);
52-
53-
int start1 = -1, end1 = -1;
54-
int merge_start= -1, merge_end = -1;
55-
if (start0 >= 0) {
56-
merge_start = start0 / 2;
57-
} else {
58-
start1 = -start0 - 1;
59-
merge_start = start1 / 2;
60-
}
61-
62-
if (end0 >= 0) {
63-
merge_end = end0 / 2;
64-
} else {
65-
end1 = -end0 - 1;
66-
if (end1 % 2 == 0) {
67-
merge_end = end1 / 2 > 0 ? end1 / 2 - 1 : 0;
68-
} else {
69-
merge_end = end1 / 2;
27+
int **results = malloc((intervalsSize + 1) * sizeof(int *));
28+
results[0] = malloc(2 * sizeof(int));
29+
results[0][0] = tmp[0];
30+
results[0][1] = tmp[1];
31+
for (i = 1; i < intervalsSize + 1; i++) {
32+
results[i] = malloc(2 * sizeof(int));
33+
if (tmp[i * 2] > results[len][1]) {
34+
len++;
35+
results[len][0] = tmp[i * 2];
36+
results[len][1] = tmp[i * 2 + 1];
37+
} else if (tmp[i * 2 + 1] > results[len][1]) {
38+
results[len][1] = tmp[i * 2 + 1];
7039
}
7140
}
72-
73-
if (merge_start == merge_end) {
74-
if (start0 < 0 && end0 < 0 && start1 == end1 && start1 % 2 == 0) {
75-
count = intervalsSize + 1;
76-
p = malloc(count * sizeof(*p));
77-
memcpy(p, intervals, merge_start * sizeof(*p));
78-
p[merge_start] = newInterval;
79-
memcpy(p + merge_start + 1, intervals + merge_start, (intervalsSize - merge_start) * sizeof(*p));
80-
} else {
81-
count = intervalsSize;
82-
p = malloc(count * sizeof(*p));
83-
memcpy(p, intervals, count * sizeof(*p));
84-
if (start0 < 0 && start1 % 2 == 0) {
85-
p[merge_start].start = newInterval.start;
86-
}
87-
if (end0 < 0 && end1 % 2 == 0) {
88-
p[merge_end].end = newInterval.end;
89-
}
90-
}
91-
} else {
92-
count = intervalsSize - (merge_end - merge_start);
93-
p = malloc(count * sizeof(*p));
94-
memcpy(p, intervals, merge_start * sizeof(*p));
95-
memcpy(p + merge_start, intervals + merge_end, (intervalsSize - merge_end) * sizeof(*p));
96-
if (start0 < 0 && start1 % 2 == 0) {
97-
p[merge_start].start = newInterval.start;
98-
} else {
99-
p[merge_start].start = intervals[merge_start].start;
100-
}
101-
if (end0 < 0 && end1 % 2 == 0) {
102-
p[merge_start].end = newInterval.end;
103-
} else {
104-
p[merge_start].end = intervals[merge_end].end;
105-
}
41+
42+
len += 1;
43+
*returnSize = len;
44+
*returnColumnSizes = malloc(len * sizeof(int));
45+
for (i = 0; i < len; i++) {
46+
(*returnColumnSizes)[i] = 2;
10647
}
107-
108-
free(nums);
109-
*returnSize = count;
110-
return p;
48+
49+
return results;
11150
}
11251

11352
int main(int argc, char **argv)
@@ -117,23 +56,24 @@ int main(int argc, char **argv)
11756
exit(-1);
11857
}
11958

120-
struct Interval new_interv;
121-
new_interv.start = atoi(argv[1]);
122-
new_interv.end = atoi(argv[2]);
59+
int new_interv[2];
60+
new_interv[0] = atoi(argv[1]);
61+
new_interv[1] = atoi(argv[2]);
12362

12463
int i, count = 0;
125-
struct Interval *intervals = malloc((argc - 3) / 2 * sizeof(struct Interval));
126-
struct Interval *p = intervals;
127-
for (i = 3; i < argc; i += 2) {
128-
p->start = atoi(argv[i]);
129-
p->end = atoi(argv[i + 1]);
130-
p++;
64+
int *size = malloc((argc - 3) / 2 * sizeof(int));
65+
int **intervals = malloc((argc - 3) / 2 * sizeof(int *));
66+
for (i = 0; i < (argc - 3) / 2; i++) {
67+
intervals[i] = malloc(2 * sizeof(int));
68+
intervals[i][0] = atoi(argv[i * 2 + 3]);
69+
intervals[i][1] = atoi(argv[i * 2 + 4]);
13170
}
13271

133-
struct Interval *q = insert(intervals, (argc - 3) / 2, new_interv, &count);
72+
int *col_sizes;
73+
int **results = insert(intervals, (argc - 3) / 2, size, new_interv, 2, &count, &col_sizes);
13474
for (i = 0; i < count; i++) {
135-
printf("[%d, %d]\n", q->start, q->end);
136-
q++;
75+
printf("[%d,%d]\n", results[i][0], results[i][1]);
13776
}
77+
13878
return 0;
13979
}

0 commit comments

Comments
 (0)