diff options
-rw-r--r-- | two_best_nonoverlap_event.c | 85 | ||||
-rw-r--r-- | two_best_nonoverlap_event.py | 39 |
2 files changed, 124 insertions, 0 deletions
diff --git a/two_best_nonoverlap_event.c b/two_best_nonoverlap_event.c new file mode 100644 index 0000000..f779dd8 --- /dev/null +++ b/two_best_nonoverlap_event.c @@ -0,0 +1,85 @@ +// 2054. Two Best Non-Overlapping Events +#include "leetcode.h" + +/* + * you are given a 0-indexed 2d integer array of 'events' where 'events[i] = + * [start_time, end_time, value]'. the i'th event starts at 'start_time' and + * ends at 'end_time', and if you attend this event, you will receive a value of + * 'value'. you can choose at most two non-overlapping events to ttend such that + * the sum of their values is maximise. return this maximum sum. note that the + * start time and end time is inclusive: that is, you cannot attend two events + * where one of them starts and the other ends at the same time. more + * specifically, if you attend an event with end time 't', the next event must + * start or after 't + 1' + */ + +struct event { + int start; + int end; + int value; +}; + +int cmp_event(const void *a, const void *b) { + struct event *e1 = (struct event *)a; + struct event *e2 = (struct event *)b; + if (e1->end == e2->end) + return e1->start - e2->start; + return e1->end < e2->end ? -1 : 1; +} + +int bin_search(struct event *e, int size, int start_time) { + int left = 0, right = size - 1, res = -1; + while (left <= right) { + int mid = left + (right - left) / 2; + if (e[mid].end < start_time) { + res = mid; + left = mid + 1; + } else + right = mid - 1; + } + return res; +} + +int maxTwoEvents(int **events, int eventsSize, int *eventsColSize) { + struct event *e = (struct event *)malloc(eventsSize * sizeof(struct event)); + for (int i = 0; i < eventsSize; i++) { + e[i].start = events[i][0]; + e[i].end = events[i][1]; + e[i].value = events[i][2]; + } + qsort(e, eventsSize, sizeof(struct event), cmp_event); + int *prefix_max = (int *)malloc(eventsSize * sizeof(int)); + prefix_max[0] = e[0].value; + for (int i = 1; i < eventsSize; i++) + prefix_max[i] = + prefix_max[i - 1] > e[i].value ? prefix_max[i - 1] : e[i].value; + int ans = 0; + for (int i = 0; i < eventsSize; i++) + if (e[i].value > ans) + ans = e[i].value; + for (int i = 0; i < eventsSize; i++) { + int idx = bin_search(e, eventsSize, e[i].start); + int prev = idx == -1 ? 0 : prefix_max[idx]; + int candidate = e[i].value + prev; + if (candidate > ans) + ans = candidate; + } + free(prefix_max), free(e); + return ans; +} + +int main() { + int e1i[3][3] = {{1, 3, 2}, {4, 5, 2}, {2, 4, 3}}, + e2i[3][3] = {{1, 3, 2}, {4, 5, 2}, {1, 5, 5}}, + e3i[3][3] = {{1, 5, 3}, {1, 5, 1}, {6, 6, 5}}; + struct two_d_arr e1, e2, e3; + two_d_arr_init(&e1, 3, 3, e1i); + two_d_arr_init(&e2, 3, 3, e2i); + two_d_arr_init(&e3, 3, 3, e3i); + printf("%d\n", maxTwoEvents(e1.arr, e1.row_size, e1.col_size)); // expect: 4 + printf("%d\n", maxTwoEvents(e2.arr, e2.row_size, e2.col_size)); // expect: 5 + printf("%d\n", maxTwoEvents(e3.arr, e3.row_size, e3.col_size)); // expect: 8 + two_d_arr_free(&e1); + two_d_arr_free(&e2); + two_d_arr_free(&e3); +} diff --git a/two_best_nonoverlap_event.py b/two_best_nonoverlap_event.py new file mode 100644 index 0000000..7b514b7 --- /dev/null +++ b/two_best_nonoverlap_event.py @@ -0,0 +1,39 @@ +# 2054. Two Best Non-Overlapping Events + +""" +you are given a 0-indexed 2d integer array of 'events' where 'events[i] = +[start_time, end_time, value]'. the i'th event starts at 'start_time' and +ends at 'end_time', and if you attend this event, you will receive a value of +'value'. you can choose at most two non-overlapping events to ttend such that +the sum of their values is maximise. return this maximum sum. note that the +start time and end time is inclusive: that is, you cannot attend two events +where one of them starts and the other ends at the same time. more +specifically, if you attend an event with end time 't', the next event must +start or after 't + 1' +""" + + +class Solution(object): + def maxTwoEvents(self, events): + """ + :type events: List[List[int]] + :rtype: int + """ + proc, ans, m = [], 0, 0 + for s, e, v in events: + proc.append((s, True, v)) + proc.append((e + 1, False, v)) + proc.sort() + for time, start, val in proc: + if start: + ans = max(ans, m + val) + else: + m = max(m, val) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxTwoEvents(events=[[1, 3, 2], [4, 5, 2], [2, 4, 3]])) + print(obj.maxTwoEvents(events=[[1, 3, 2], [4, 5, 2], [1, 5, 5]])) + print(obj.maxTwoEvents(events=[[1, 5, 3], [1, 5, 1], [6, 6, 5]])) |