Simple Intuitive Greedy (Beats 97% TE and 77% ME)
Intuition\nIf people in a friendship are able to communicate with each other with at least 1 language, we do not care about them here.\nBut if they are not able
# Intuition\nIf people in a friendship are able to communicate with each other with at least 1 language, we do not care about them here.\nBut if they are not able to communicate, we need to find the language which is most popular amoung this set and the number of speakers of that language. We will need to teach the others this popular language.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution:\n    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:\n        languages = [set(l) for l in languages]\n        dontspeak = set()\n        langs = defaultdict(int)\n        poplang = n\n        speakers = 0\n        for i, j in friendships:\n            lang1 = languages[i-1]\n            lang2 = languages[j-1]\n\n            if lang1 & lang2: continue\n            \n            if i not in dontspeak:\n                for k in lang1:\n                    langs[k]+=1\n                    if langs[k]>speakers:\n                        poplang = k\n                        speakers=langs[k]\n            if j not in dontspeak:\n                for k in lang2:\n                    langs[k]+=1\n                    if langs[k]>speakers:\n                        poplang = k\n                        speakers=langs[k]\n\n            dontspeak.add(i)\n            dontspeak.add(j)\n\n        return len(dontspeak)-speakers\n\n\n```
['Greedy', 'Python3']