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 /min_num_people_teach.py | |
parent | d782a5138b047c6ee14bded264a1af24fbcfcb4d (diff) | |
download | leetcode-a675ae1a71ab3e88196a2a72a62f2c7a0d4c596a.tar.gz leetcode-a675ae1a71ab3e88196a2a72a62f2c7a0d4c596a.zip |
1733. minimum number of people to teach
Diffstat (limited to 'min_num_people_teach.py')
-rw-r--r-- | min_num_people_teach.py | 61 |
1 files changed, 61 insertions, 0 deletions
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]], + ) + ) |