1 <= m <= 500

1 <= languages[i].length <= n

1 <= languages[i][j] <= n

1 <= ui < vi <= languages.length

1 <= friendships.length <= 500

All tuples (ui, vi) are unique

languages[i] contains only unique values

Solution

Method 1 – Greedy Language Selection

Intuition

For each friendship, if the two users do not share a language, we must teach one language to at least one of them. To minimize the number of people to teach, try each language and count how many users need to learn it so all friendships are covered.

Approach

For each friendship, check if the two users share a language. If not, add both to a set of candidates.
For each language, count how many candidates do not know it.
The answer is the minimum such count over all languages.

Code

[{"language":"C++","code":"using namespace std;\nclass Solution {\npublic:\n    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {\n        int m = languages.size();\n        vector<unordered_set<int>> knows(m);\n        for (int i = 0; i < m; ++i)\n            for (int l : languages[i]) knows[i].insert(l);\n        unordered_set<int> candidates;\n        for (auto& f : friendships) {\n            int u = f[0] - 1, v = f[1] - 1;\n            bool ok = false;\n            for (int l : knows[u]) if (knows[v].count(l)) { ok = true; break; }\n            if (!ok) { candidates.insert(u); candidates.insert(v); }\n        }\n        int res = m;\n        for (int l = 1; l <= n; ++l) {\n            int cnt = 0;\n            for (int u : candidates) if (!knows[u].count(l)) cnt++;\n            res = min(res, cnt);\n        }\n        return res;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F9758

Related Tags