Minimum Number of People to Teach
Problem
Given n languages, languages[i] of user i+1, and friendship pairs, teach one language to the minimum number of users so every friendship has a common language.
n=2, languages=[[1],[2],[1,2]], friendships=[[1,2],[1,3],[2,3]]1def minimum_teachings(n, languages, friendships):
L = [set(l) for l in languages]
bad_users = set()
for u, v in friendships:
if not (L[u-1] & L[v-1]):
bad_users.add(u-1); bad_users.add(v-1)
from collections import Counter
cnt = Counter()
for u in bad_users:
for lang in L[u]: cnt[lang] += 1
if not bad_users: return 0
return len(bad_users) - max(cnt.values())function minimumTeachings(n, languages, friendships) {
const L = languages.map(l => new Set(l));
const bad = new Set();
for (const [u, v] of friendships) {
let ok = false;
for (const x of L[u-1]) if (L[v-1].has(x)) { ok = true; break; }
if (!ok) { bad.add(u-1); bad.add(v-1); }
}
if (!bad.size) return 0;
const cnt = new Map();
for (const u of bad) for (const x of L[u]) cnt.set(x, (cnt.get(x) || 0) + 1);
let mx = 0; for (const v of cnt.values()) mx = Math.max(mx, v);
return bad.size - mx;
}class Solution {
public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
Set<Integer> bad = new HashSet<>();
for (int[] f : friendships) {
Set<Integer> a = new HashSet<>(); for (int x : languages[f[0]-1]) a.add(x);
boolean ok = false; for (int x : languages[f[1]-1]) if (a.contains(x)) { ok = true; break; }
if (!ok) { bad.add(f[0]-1); bad.add(f[1]-1); }
}
if (bad.isEmpty()) return 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int u : bad) for (int x : languages[u]) cnt.merge(x, 1, Integer::sum);
int mx = 0; for (int v : cnt.values()) mx = Math.max(mx, v);
return bad.size() - mx;
}
}int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
int m = languages.size();
vector<unordered_set<int>> L(m);
for (int i = 0; i < m; i++) for (int x : languages[i]) L[i].insert(x);
unordered_set<int> bad;
for (auto& f : friendships) {
bool ok = false;
for (int x : L[f[0]-1]) if (L[f[1]-1].count(x)) { ok = true; break; }
if (!ok) { bad.insert(f[0]-1); bad.insert(f[1]-1); }
}
if (bad.empty()) return 0;
unordered_map<int,int> cnt;
for (int u : bad) for (int x : languages[u]) cnt[x]++;
int mx = 0; for (auto& p : cnt) mx = max(mx, p.second);
return (int)bad.size() - mx;
}Explanation
You only have to fix the friendships that are actually broken — pairs of friends who currently share no common language. The clever part is that you may teach exactly one language to as many people as you like, so the whole job is: pick the single best language and teach it to everyone who needs it.
First we find the trouble. Each user's languages are stored as a set, so for a friendship (u, v) we just check if L[u-1] & L[v-1] is empty. If it is, both users go into a bad_users set — these are the only people we might teach.
Now which language to teach? If we teach language X, the people we still have to teach are the bad users who don't already know X. So we count, among bad users, how many already know each language (a Counter), and the best language is the one most of them already have. The answer is len(bad_users) - max(count) — total troubled people minus the ones we get for free.
Example: users know [1], [2], [1,2] and all three are mutual friends. The pair (1,2) shares nothing, so users 1 and 2 are bad. Each of those two knows a different language, so the best we save is 1, giving 2 - 1 = 1 person to teach.
If no friendship is broken, bad_users is empty and we return 0 immediately.