aboutsummaryrefslogtreecommitdiff
path: root/min_num_people_teach.c
blob: 5acbf5e5417ac6498f092bbe43cd9ba03fbf2cd8 (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
// 1733. Minimum Number of People to Teach
#include "leetcode.h"

/*
 * on a social network consisting of 'm' users and some friendships between
 * users, two users can communicate with each other if they know a common
 * language. you are given an integer 'n', an array 'languages', and an array
 * 'friendships' where there are 'n' languages numbered 1 through 'n',
 * 'languages[i]' is the set of languages the i'th user knows, and
 * 'friendships[i] = [ui, vi]' denotes a friendship between the users 'ui' and
 * 'vi'. you can choose one language and teach it to some users so that all
 * friends can communicate with eachother. return the minimum number of users
 * you need to teach. note that friendships are not transitive, meaning if 'x'
 * is a friend of 'y' and 'y' is a friend of 'z', this doesn't guarantee 'x' is
 * a friend of 'z'.
 */

int minimumTeachings(int n, int **languages, int languagesSize,
                     int *languagesColSize, int **friendships,
                     int friendshipsSize, int *friendshipsColSize) {
  bool need[505] = {false};
  for (int i = 0; i < friendshipsSize; i++) {
    int u = friendships[i][0] - 1;
    int v = friendships[i][1] - 1;
    bool valid = false;
    for (int j = 0; j < languagesColSize[u]; j++) {
      for (int k = 0; k < languagesColSize[v]; k++)
        if (languages[u][j] == languages[v][k]) {
          valid = true;
          break;
        }
      if (valid)
        break;
    }
    if (!valid)
      need[u] = need[v] = true;
  }
  int ans = languagesSize + 1;
  for (int i = 1; i <= n; i++) {
    int candidate = 0;
    for (int j = 0; j < languagesSize; j++) {
      if (need[j]) {
        bool found = false;
        for (int k = 0; k < languagesColSize[j]; k++)
          if (languages[j][k] == i) {
            found = true;
            break;
          }
        if (!found)
          candidate++;
      }
    }
    if (candidate < ans)
      ans = candidate;
  }
  return ans;
}

int main() {
  int l1i[3][2] = {{1}, {2}, {1, 2}}, lcs1[] = {};
  int f1i[3][2] = {{1, 2}, {1, 3}, {2, 3}};
  int l2i[4][2] = {{2}, {1, 3}, {1, 2}, {3}}, lcs2[] = {};
  int f2i[4][2] = {{1, 4}, {1, 2}, {3, 4}, {2, 3}};
  for (int i = 0; i < ARRAY_SIZE(l1i); i++)
    lcs1[i] = ARRAY_SIZE(l1i[i]);
  for (int i = 0; i < ARRAY_SIZE(l2i); i++)
    lcs2[i] = ARRAY_SIZE(l2i[i]);
  struct two_d_arr *l1 =
      two_d_arr_init(ARRAY_SIZE(l1i), ARRAY_SIZE(l1i[2]), l1i);
  struct two_d_arr *f1 =
      two_d_arr_init(ARRAY_SIZE(f1i), ARRAY_SIZE(f1i[0]), f1i);
  struct two_d_arr *l2 =
      two_d_arr_init(ARRAY_SIZE(l2i), ARRAY_SIZE(l2i[1]), l2i);
  struct two_d_arr *f2 =
      two_d_arr_init(ARRAY_SIZE(f2i), ARRAY_SIZE(f2i[0]), f2i);
  printf("%d\n", minimumTeachings(2, l1->arr, l1->row_size, lcs1, f1->arr,
                                  f1->row_size, f1->col_size)); // expect: 1
  printf("%d\n", minimumTeachings(3, l2->arr, l2->row_size, lcs2, f2->arr,
                                  f2->row_size, f2->col_size)); // expect: 2
  two_d_arr_free(l1);
  two_d_arr_free(f1);
  two_d_arr_free(l2);
  two_d_arr_free(f2);
}