1733. Minimum Number of People to Teach
思路 :
先把friendship裡面可以溝通的組合刪掉
算出剩下的人幾個假設有m個
並統計剩下來的每個人會講的語言
找出最多人會講的語言 : L
假設剩下來的人中有x個人會講L語言
那答案就是L-x
golang code :
func minimumTeachings(n int, languages [][]int, friendships [][]int) int {
m := len(languages)
know := make([]map[int]bool, m+1)
for i, val := range languages {
people := i + 1
know[people] = make(map[int]bool)
for _, language := range val {
know[people][language] = true
}
}
needTeach := make(map[int]bool)
for _, f := range friendships {
u, v := f[0], f[1]
teach := true
for language := range know[u] {
if know[v][language] {
teach = false
break
}
}
if teach {
needTeach[u] = true
needTeach[v] = true
}
}
NumNeedTeach := len(needTeach)
if NumNeedTeach == 0 {
return 0
}
arr := make(map[int]int)
for i, val := range languages {
people := i + 1
if needTeach[people] {
for _, language := range val {
arr[language]++
}
}
}
L := 0
for _, val := range arr {
L = max(val,L)
}
return NumNeedTeach-L
}

大師