diff options
author | Jack Sangdahl <[email protected]> | 2024-12-07 20:06:11 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-07 20:06:11 -0700 |
commit | d34ae6f5f41456a4f6cf6f3e26b8bf0fb285c263 (patch) | |
tree | deaea8ed72e4990fec7d95734fd2dcf36b0a6290 /two_best_nonoverlap_event.py | |
parent | 4bf9dfaf017f75a45b8acb6fce5a6624fdb91b41 (diff) | |
download | leetcode-d34ae6f5f41456a4f6cf6f3e26b8bf0fb285c263.tar.gz leetcode-d34ae6f5f41456a4f6cf6f3e26b8bf0fb285c263.zip |
2054. two best non overlapping events
Diffstat (limited to 'two_best_nonoverlap_event.py')
-rw-r--r-- | two_best_nonoverlap_event.py | 39 |
1 files changed, 39 insertions, 0 deletions
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]])) |