diff options
author | Jack Sangdahl <[email protected]> | 2025-09-09 19:20:15 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-09 19:20:15 -0600 |
commit | a675ae1a71ab3e88196a2a72a62f2c7a0d4c596a (patch) | |
tree | 973ee7801e9f0c25e168ab1f854c6096c760212c | |
parent | d782a5138b047c6ee14bded264a1af24fbcfcb4d (diff) | |
download | leetcode-a675ae1a71ab3e88196a2a72a62f2c7a0d4c596a.tar.gz leetcode-a675ae1a71ab3e88196a2a72a62f2c7a0d4c596a.zip |
1733. minimum number of people to teach
-rw-r--r-- | min_num_people_teach.c | 84 | ||||
-rw-r--r-- | min_num_people_teach.py | 61 |
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]], + ) + ) |