Minimum Number of People to Teach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
        ans = inf
        languages = [set(x) for x in languages]

        for language in range(1, n+1):
            curr, seen = 0, set()

            for a,b in friendships:
                if len(languages[a-1] & languages[b-1]) == 0: # if no common languaes i.e, friends cannot communicate

                    if language not in languages[a-1] and a not in seen:
                        curr += 1
                        seen.add(a)
                    if language not in languages[b-1] and b not in seen:
                        curr += 1
                        seen.add(b)

                if curr >= ans: break # Early break condition 

            ans = min(ans, curr)
        return ans