aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-08 00:37:56 -0600
committerJack Sangdahl <[email protected]>2025-07-08 00:37:56 -0600
commitf9b8fbe80847469abc73afb3ffe350361571bf70 (patch)
tree40fc53257fa0503c8a4de36c5b97e3a67f713e74
parenta46ef4d0be2f3eb1384b222b5a2bf5091d9c3be3 (diff)
downloadleetcode-f9b8fbe80847469abc73afb3ffe350361571bf70.tar.gz
leetcode-f9b8fbe80847469abc73afb3ffe350361571bf70.zip
1751. maximum number of events that can be attended 2HEADmaster
-rw-r--r--max_num_events_attended2.c71
-rw-r--r--max_num_events_attended2.py39
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))