diff options
-rw-r--r-- | max_num_events_attended2.c | 71 | ||||
-rw-r--r-- | max_num_events_attended2.py | 39 |
2 files changed, 110 insertions, 0 deletions
diff --git a/max_num_events_attended2.c b/max_num_events_attended2.c new file mode 100644 index 0000000..ad9bfdb --- /dev/null +++ b/max_num_events_attended2.c @@ -0,0 +1,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); +} diff --git a/max_num_events_attended2.py b/max_num_events_attended2.py new file mode 100644 index 0000000..d6a33c9 --- /dev/null +++ b/max_num_events_attended2.py @@ -0,0 +1,39 @@ +# 1751. Maximum Number of Events That Can Be Attended II +from bisect import bisect + +""" +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 +""" + + +class Solution(object): + def maxValue(self, events, k): + """ + :type events: List[List[int]] + :type k: int + :rtype: int + """ + events.sort(key=lambda x: x[1]) + dp1, dp2 = [[0, 0]], [[0, 0]] + for i in range(k): + for s, e, v in events: + j = bisect(dp1, [s]) - 1 + if dp1[j][1] + v > dp2[-1][1]: + dp2.append([e, dp1[j][1] + v]) + dp1, dp2 = dp2, [[0, 0]] + return dp1[-1][-1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxValue(events=[[1, 2, 4], [3, 4, 3], [2, 3, 1]], k=2)) + print(obj.maxValue(events=[[1, 2, 4], [3, 4, 3], [2, 3, 10]], k=2)) + print(obj.maxValue(events=[[1, 1, 1], [2, 2, 2], [3, 3, 3], [4, 4, 4]], k=3)) |