leetcode

commit 4eb955fc2d278c9acbb3071f3b3866b887f356c7
parent 70e7750f0729ea05fdcf95dcc876e415c69ecbfa
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon, 22 Dec 2025 20:01:02 -0700

2054. two best non-overlapping events

Diffstat:
M
two_best_nonoverlap_event.c
 | 
85
++++++++++++++++++++++++++++++-------------------------------------------------

1 file changed, 32 insertions(+), 53 deletions(-)
diff --git a/two_best_nonoverlap_event.c b/two_best_nonoverlap_event.c
@@ -13,68 +13,47 @@
  * 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 cmp(const void *a, const void *b) {
+  int *aa = *(int **)a;
+  int *bb = *(int **)b;
+  return aa[1] - bb[1];
 }
 
 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;
+  qsort(events, eventsSize, sizeof(int *), cmp);
+  int curr_max = 0, global_max = 0;
+  int *max_vals = (int *)malloc(eventsSize * sizeof(int));
+  max_vals[0] = events[0][2];
   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;
+    max_vals[i] = fmax(max_vals[i - 1], events[i][2]);
   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;
+    int start = events[i][0], value = events[i][2];
+    int low = 0, high = i - 1, idx = -1;
+    while (low <= high) {
+      int mid = low + (high - low) / 2;
+      if (events[mid][1] <= start - 1) {
+        idx = mid;
+        low = mid + 1;
+      } else
+        high = mid - 1;
+    }
+    curr_max = idx != -1 ? value + max_vals[idx] : value;
+    global_max = fmax(global_max, curr_max);
   }
-  free(prefix_max), free(e);
-  return ans;
+  free(max_vals);
+  return global_max;
 }
 
 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 = two_d_arr_init(3, 3, e1i);
-  struct two_d_arr *e2 = two_d_arr_init(3, 3, e2i);
-  struct two_d_arr *e3 = two_d_arr_init(3, 3, e3i);
+  int e1i[3][3] = {{1, 3, 2}, {4, 5, 2}, {2, 4, 3}};
+  int e2i[3][3] = {{1, 3, 2}, {4, 5, 2}, {1, 5, 5}};
+  int e3i[3][3] = {{1, 5, 3}, {1, 5, 1}, {6, 6, 5}};
+  struct two_d_arr *e1 =
+      two_d_arr_init(ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
+  struct two_d_arr *e2 =
+      two_d_arr_init(ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
+  struct two_d_arr *e3 =
+      two_d_arr_init(ARRAY_SIZE(e3i), ARRAY_SIZE(e3i[0]), e3i);
   printf("%d\n",
          maxTwoEvents(e1->arr, e1->row_size, e1->col_size)); // expect: 4
   printf("%d\n",