aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--min_num_people_teach.c84
-rw-r--r--min_num_people_teach.py61
2 files changed, 145 insertions, 0 deletions
diff --git a/min_num_people_teach.c b/min_num_people_teach.c
new file mode 100644
index 0000000..5acbf5e
--- /dev/null
+++ b/min_num_people_teach.c
@@ -0,0 +1,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);
+}
diff --git a/min_num_people_teach.py b/min_num_people_teach.py
new file mode 100644
index 0000000..6285d1b
--- /dev/null
+++ b/min_num_people_teach.py
@@ -0,0 +1,61 @@
+# 1733. Minimum Number of People to Teach
+
+"""
+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'.
+"""
+
+
+class Solution(object):
+ def minimumTeachings(self, n, languages, friendships):
+ """
+ :type n: int
+ :type languages: List[List[int]]
+ :type friendships: List[List[int]]
+ :rtype: int
+ """
+ need = set()
+ for u, v in friendships:
+ u -= 1
+ v -= 1
+ valid = False
+ for i in languages[u]:
+ if i in languages[v]:
+ valid = True
+ break
+ if not valid:
+ need.add(u)
+ need.add(v)
+ ans = len(languages) + 1
+ for i in range(1, n + 1):
+ candidate = 0
+ for j in need:
+ if i not in languages[j]:
+ candidate += 1
+ ans = min(ans, candidate)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.minimumTeachings(
+ n=2, languages=[[1], [2], [1, 2]], friendships=[[1, 2], [1, 3], [2, 3]]
+ )
+ )
+ print(
+ obj.minimumTeachings(
+ n=3,
+ languages=[[2], [1, 3], [1, 2], [3]],
+ friendships=[[1, 4], [1, 2], [3, 4], [2, 3]],
+ )
+ )