aboutsummaryrefslogtreecommitdiff
path: root/best_team_no_conflict.c
blob: 15f27e307bda05764582b1373e8c580e1595f186 (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
// 1626. Best Team With No Conflicts
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

/*
 * you are manager of a basketball team. for upcoming tournament you want to
 * choose the team with the highest overall score. the score of the team is the
 * sum of scores of all the players in the team. however the basketball team is
 * not allowed to have conflicts. a conflict exists if a younger player has a
 * strictly high score than an older player. a conflict does not occur between
 * players of the same age. given two lists, 'scores', & 'ages', where each
 * 'scores[i]' and 'ages[i]' represents the score and age of the ith player
 * respectively. return highest overall score of all teams.
 */

int cmp(const void *a, const void *b) {
  int *aa = *(int **)a;
  int *bb = *(int **)b;
  if (aa[0] == bb[0])
    return aa[1] - bb[1];
  return aa[0] - bb[0];
}

int bestTeamScore(int *scores, int scoresSize, int *ages, int agesSize) {
  int n = scoresSize;
  int **data = malloc(n * sizeof(int *));
  for (int i = 0; i < n; i++) {
    data[i] = malloc(2 * sizeof(int));
    data[i][0] = ages[i];
    data[i][1] = scores[i];
  }
  qsort(data, n, sizeof(int *), cmp);
  int *dp = malloc(n * sizeof(int));
  dp[0] = data[0][1];
  int ans = dp[0];
  for (int i = 1; i < n; i++) {
    int pre = INT_MIN;
    dp[i] = data[i][1];
    for (int j = 0; j < i; j++)
      if (data[j][i] <= data[i][1])
        pre = fmax(pre, dp[j]);
    if (pre != INT_MIN)
      dp[i] += pre;
    ans = fmax(ans, dp[i]);
  }
  free(dp);
  for (int i = 0; i < n; i++)
    free(data[i]);
  free(data);
  return ans;
}

int main() {
  int scores1[] = {1, 3, 5, 10, 15}, ages1[] = {1, 2, 3, 4, 5};
  int scores2[] = {4, 5, 6, 5}, ages2[] = {2, 1, 2, 1};
  int scores3[] = {1, 2, 3, 5}, ages3[] = {8, 9, 10, 1};
  printf("%d\n", bestTeamScore(scores1, 5, ages1, 5)); // expect: 34
  printf("%d\n", bestTeamScore(scores2, 4, ages1, 4)); // expect: 16
  printf("%d\n", bestTeamScore(scores3, 4, ages1, 4)); // expect: 6
}