aboutsummaryrefslogtreecommitdiff
path: root/max_num_events_attended2.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_num_events_attended2.py')
-rw-r--r--max_num_events_attended2.py39
1 files changed, 39 insertions, 0 deletions
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))