# 1733. Minimum Number of People to Teach¶

• Time: $O(mn)$
• Space: $O(m + n)$
  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 class Solution { public: int minimumTeachings(int n, vector>& languages, vector>& friendships) { vector> languageSets; unordered_set needTeach; unordered_map languageCount; for (const vector& language : languages) languageSets.push_back({language.begin(), language.end()}); // Find friends that can't communicate. for (const vector& friendship : friendships) { const int u = friendship[0] - 1; const int v = friendship[1] - 1; if (cantTalk(languageSets, u, v)) { needTeach.insert(u); needTeach.insert(v); } } // Find the most popular language. for (const int u : needTeach) for (const int language : languageSets[u]) ++languageCount[language]; // Teach the most popular language to people who don't understand. int maxCount = 0; for (const auto& [_, freq] : languageCount) maxCount = max(maxCount, freq); return needTeach.size() - maxCount; } private: // Returns true if u can't talk with v. bool cantTalk(const vector>& languageSets, int u, int v) { for (const int language : languageSets[u]) if (languageSets[v].count(language)) return false; return true; } }; 
  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 class Solution { public int minimumTeachings(int n, int[][] languages, int[][] friendships) { List> languageSets = new ArrayList<>(); Set needTeach = new HashSet<>(); Map languageCount = new HashMap<>(); for (int[] language : languages) languageSets.add(new HashSet<>(Arrays.stream(language).boxed().toList())); // Find friends that can't communicate. for (int[] friendship : friendships) { final int u = friendship[0] - 1; final int v = friendship[1] - 1; if (cantTalk(languageSets, u, v)) { needTeach.add(u); needTeach.add(v); } } // Find the most popular language. for (int u : needTeach) for (final int language : languageSets.get(u)) languageCount.merge(language, 1, Integer::sum); // Teach the most popular language to people who don't understand. int maxCount = 0; for (int freq : languageCount.values()) maxCount = Math.max(maxCount, freq); return needTeach.size() - maxCount; } // Returns true if u can't talk with v. private boolean cantTalk(List> languageSets, int u, int v) { for (int language : languageSets.get(u)) if (languageSets.get(v).contains(language)) return false; return true; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int: languageSets = [set(languages) for languages in languages] needTeach = set() languageCount = collections.Counter() # Find friends that can't communicate. for u, v in friendships: if not languageSets[u - 1] & languageSets[v - 1]: needTeach.add(u - 1) needTeach.add(v - 1) # Find the most popular language. for u in needTeach: for language in languageSets[u]: languageCount[language] += 1 # Teach the most popular language to people don't understand. return len(needTeach) - max(languageCount.values(), default=0)