aboutsummaryrefslogtreecommitdiff
path: root/max_num_events_attended2.c
blob: ad9bfdbe965082dba0eb65abd80686767f173267 (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
// 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);
}