aboutsummaryrefslogtreecommitdiff
path: root/min_num_people_teach.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-09 19:20:15 -0600
committerJack Sangdahl <[email protected]>2025-09-09 19:20:15 -0600
commita675ae1a71ab3e88196a2a72a62f2c7a0d4c596a (patch)
tree973ee7801e9f0c25e168ab1f854c6096c760212c /min_num_people_teach.py
parentd782a5138b047c6ee14bded264a1af24fbcfcb4d (diff)
downloadleetcode-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.py61
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]],
+ )
+ )