aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_num_events_attended.c9
-rw-r--r--max_num_events_attended.py37
2 files changed, 46 insertions, 0 deletions
diff --git a/max_num_events_attended.c b/max_num_events_attended.c
new file mode 100644
index 0000000..9a6daef
--- /dev/null
+++ b/max_num_events_attended.c
@@ -0,0 +1,9 @@
+#include "leetcode.h"
+
+/*
+ * you are given an array of 'events' where 'events[i] = [startday_i,
+ * endday_i]'. every event 'i' starts at 'startday_i' and ends at 'endday_i'.
+ * you can attend an event 'i' at any day 'd' where 'starttime_i <= d <=
+ * endtime_i'. you can only attend one event at any time 'd'. return the maximum
+ * number of events you can attend.
+ */
diff --git a/max_num_events_attended.py b/max_num_events_attended.py
new file mode 100644
index 0000000..1aaf591
--- /dev/null
+++ b/max_num_events_attended.py
@@ -0,0 +1,37 @@
+# 1353. Maximum Number of Events That Can Be Attended
+import heapq
+
+"""
+you are given an array of 'events' where 'events[i] = [startday_i,
+endday_i]'. every event 'i' starts at 'startday_i' and ends at 'endday_i'.
+you can attend an event 'i' at any day 'd' where 'starttime_i <= d <=
+endtime_i'. you can only attend one event at any time 'd'. return the maximum
+number of events you can attend.
+"""
+
+
+class Solution(object):
+ def maxEvents(self, events):
+ """
+ :type events: List[List[int]]
+ :rtype: int
+ """
+ events.sort(reverse=True)
+ heap, ans, d = [], 0, 0
+ while events or heap:
+ if not heap:
+ d = events[-1][0]
+ while events and events[-1][0] <= d:
+ heapq.heappush(heap, events.pop()[1])
+ heapq.heappop(heap)
+ ans += 1
+ d += 1
+ while heap and heap[0] < d:
+ heapq.heappop(heap)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxEvents(events=[[1, 2], [2, 3], [3, 4]]))
+ print(obj.maxEvents(events=[[1, 2], [2, 3], [3, 4], [1, 2]]))