aboutsummaryrefslogtreecommitdiff
path: root/two_best_nonoverlap_event.c
blob: f779dd811e9e48ae9818fbae5c60619ddfcc953f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 2054. Two Best Non-Overlapping Events
#include "leetcode.h"

/*
 * 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'
 */

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 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;
  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;
  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;
  }
  free(prefix_max), free(e);
  return ans;
}

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, e2, e3;
  two_d_arr_init(&e1, 3, 3, e1i);
  two_d_arr_init(&e2, 3, 3, e2i);
  two_d_arr_init(&e3, 3, 3, e3i);
  printf("%d\n", maxTwoEvents(e1.arr, e1.row_size, e1.col_size)); // expect: 4
  printf("%d\n", maxTwoEvents(e2.arr, e2.row_size, e2.col_size)); // expect: 5
  printf("%d\n", maxTwoEvents(e3.arr, e3.row_size, e3.col_size)); // expect: 8
  two_d_arr_free(&e1);
  two_d_arr_free(&e2);
  two_d_arr_free(&e3);
}