โปรแกรมหาจำนวนคนน้อยที่สุดที่ต้องสอนภาษาใน Python

มี n ภาษา, languages[i] = ภาษาที่คน i รู้, friendships = คู่เพื่อน สอนภาษา 1 ภาษาให้บางคน เพื่อให้เพื่อนทุกคู่สื่อสารได้ ต้องหาจำนวนคนน้อยที่สุดที่ต้องสอน

ตัวอย่าง: n=3, languages=[[2],[1,3],[1,2],[3]], friendships=[[1,4],[1,2],[3,4],[2,3]] ผลลัพธ์ 2 (สอนภาษา 3 ให้คน 1 และ 3)

วิธีแก้ปัญหา

1. หาคู่เพื่อนที่ ไม่ สื่อสารได้ (ภาษาไม่ซ้อนกัน) → เก็บคนเหล่านั้นใน not_comm
2. นับความถี่ภาษาของคนใน not_comm
3. คืน len(not_comm) - max_frequency

ตัวอย่างโค้ด

from collections import Counter

def solve(n, languages, friendships):
    lang = [set(L) for L in languages]
    not_comm = set()
    for a,b in friendships:
        a -= 1; b -= 1
        if lang[a].isdisjoint(lang[b]):
            not_comm.add(a)
            not_comm.add(b)
    if not not_comm: return 0
    cnt = Counter()
    for person in not_comm:
        cnt.update(lang[person])
    temp = max(cnt.values())
    return len(not_comm) - temp

n = 3
languages = [[2],[1,3],[1,2],[3]]
friendships = [[1,4],[1,2],[3,4],[2,3]]
print(solve(n, languages, friendships))

อินพุต

3, [[2],[1,3],[1,2],[3]], [[1,4],[1,2],[3,4],[2,3]]

เอาต์พุต

2