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
64
65
66
67
68
69
70
71
|
// 1751. Maximum Number of Events That Can Be Attended II
#include "leetcode.h"
/*
* you are given an array of 'events' where 'events[i] = [startday_i, endday_i,
* value_i]'. the i'th event starts at 'startday_i' and ends at 'endday_i', and
* if you attend this event, you will receive a value of 'value_i'. you are also
* given an integer 'k', which represents the maximum number of events you can
* attend. you can only attend one event at a time. if you choose to attend an
* event, you must attend the entire event. note that the end day is inclusive:
* that is, you cannot attend two events where one of them starts and the other
* ends on the same day. return the maximum sum of the values that you can
* receive by attending events
*/
int cmp(const void *a, const void *b) {
return (*(int **)a)[1] - (*(int **)b)[1];
}
int prev_event(int **events, int size, int deadline) {
int start = 0, end = size - 1;
while (start < end) {
int mid = start + (end - start + 1) / 2, curr = events[mid][1];
if (curr < deadline)
start = mid;
else
end = mid - 1;
}
return events[start][1] < deadline ? start : -1;
}
int maxValue(int **events, int eventsSize, int *eventsColSize, int k) {
qsort(events, eventsSize, sizeof(*events), cmp);
int **vals = (int **)malloc((k + 1) * sizeof(int *));
for (int i = 0; i < k + 1; i++)
vals[i] = (int *)malloc(eventsSize * sizeof(int));
int *prev = (int *)malloc(eventsSize * sizeof(int)), max = 0;
for (int i = 0; i != k + 1; ++i) {
for (int j = 0; j != eventsSize; ++j) {
if (!i) {
vals[i][j] = 0;
prev[j] = prev_event(events, j, events[j][0]);
} else {
int prev_max = !j ? 0 : vals[i][j - 1];
int curr = events[j][2] + (prev[j] >= 0 ? vals[i - 1][prev[j]] : 0);
vals[i][j] = prev_max > curr ? prev_max : curr;
}
}
}
int ans = vals[k][eventsSize - 1];
for (int i = 0; i < k + 1; i++)
free(vals[i]);
free(vals), free(prev);
return ans;
}
int main() {
int e1i[3][3] = {{1, 2, 4}, {3, 4, 3}, {2, 3, 1}};
int e2i[3][3] = {{1, 2, 4}, {3, 4, 3}, {2, 3, 10}};
int e3i[4][3] = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 4, 4}};
struct two_d_arr e1, e2, e3;
two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
two_d_arr_init(&e3, ARRAY_SIZE(e3i), ARRAY_SIZE(e3i[0]), e3i);
printf("%d\n", maxValue(e1.arr, e1.row_size, e1.col_size, 2)); // expect: 7
printf("%d\n", maxValue(e2.arr, e2.row_size, e2.col_size, 2)); // expect: 10
printf("%d\n", maxValue(e3.arr, e3.row_size, e3.col_size, 3)); // expect: 9
two_d_arr_free(&e1);
two_d_arr_free(&e2);
two_d_arr_free(&e3);
}
|