C++ O(n2logn) with tutorial
The Idea in this problem is the following, we have n langauges and there are m people and l pairs of people,\nwe need to find which langauge we need to make all
The Idea in this problem is the following, we have n langauges and there are m people and l pairs of people,\nwe need to find which langauge we need to make all of them be able to talk to all the people that they are paired with. \nSome Observations,\nWe dont need to consider pair of people that have at least one language in common so we can discard those pairs.\n\nNow we are left with pairs where none of the pairs have any language common in between them\n.\nNext thing to observe is we can teach only a single language & we would have to teach it to all of them those who dont know the language already. \n\nReason is as follows:\nLets say we wish to teach ith language\nnow considering 3 pairs of people,\ndon\'t know i, don\'t know i - for them to communicate both of them have to be taught\ndon\'t know i, know i, - for them to communicate one has to be taught\nknow i, know i, - for them to communicate no one has to be taught\nTherefore we teach every guy that does not know the language.\n\nNow the explaination for the code, \nWe iterate through all the pairs in friendships array and if they dont have a common language we store both the people in the set ( set is used to avoid double counting). Now we go through all the languages and check which language we need to teach minimum times and return that value.\n\n```\nbool common(vector<vector<int>>& languages, vector<int>& f){\n    int n = languages[f[0] - 1].size();\n    int m = languages[f[1] - 1].size();\n    set<int> s;\n    for(int i = 0 ; i < 2; i++){\n        for(int j = 0 ; j < languages[f[i]-1].size(); j++){\n            s.insert(languages[f[i] - 1][j]);\n        }\n    }\n    if(s.size() < n + m) return true;\n    return false;\n}\n\nbool knows(int lang, vector<int>& languages){\n    for(int i = 0 ; i < languages.size(); i++) if(lang == languages[i]) return true;\n    return false;\n}\n\nclass Solution {\npublic:\n    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {\n        int l = friendships.size();\n        int m = languages.size();\n        set<int> s;\n        // cout << 1<< endl;\n        for(int i = 0 ; i < l ; i++ ){\n            if(!common(languages, friendships[i])){\n                s.insert(friendships[i][0]);\n                s.insert(friendships[i][1]);\n            } \n        }\n        cout << 2<< endl;\n        auto it = s.begin();\n        int mine = INT_MAX;\n        for(int lang = 1; lang <= n ; lang++){\n            int counter = 0;\n            for(int i:s){\n                if(!knows(lang, languages[i-1])) counter++;\n            }\n            mine = min(mine, counter);\n        }\n        return mine;\n    }\n};\n```
[]