Python में सभी अलग-अलग कोर्स कवर करने के लिए न्यूनतम सेमेस्टर गिनने का प्रोग्राम

मान लीजिए हमारे पास एक संख्या n है, जो दर्शाती है कि 1 से n तक लेबल किए गए n अलग-अलग कोर्स हैं। हमारे पास एक ऐरे relations भी है जहां relations[i] में एक जोड़ी (prevCourse_i, nextCourse_i) होती है, जो कोर्स prevCourse_i और कोर्स nextCourse_i के बीच एक पूर्वापेक्षा संबंध को दर्शाती है: यानी कोर्स prevCourse_i को कोर्स nextCourse_i से पहले लेना होगा। और अंतिम पैरामीटर k है। एक सेमेस्टर में, हम अधिकतम k कोर्स ले सकते हैं बशर्ते हमने उन कोर्स के लिए पिछले सेमेस्टर में सभी पूर्वापेक्षाएं ले ली हों। हमें सभी कोर्स लेने के लिए आवश्यक न्यूनतम सेमेस्टर की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है: तो आउटपुट 3 होगा क्योंकि पहले सेमेस्टर में हम कोर्स 1 और 2 ले सकते हैं, अब हम कोर्स 3, 4 और 5 के लिए योग्य हैं, तो यदि हम दूसरे सेमेस्टर में 5 और 3 या 4 में से कोई एक लेते हैं, तो हम अगले सेमेस्टर में सभी कोर्स खत्म कर सकते हैं। तो हमें कुल 3 सेमेस्टर चाहिए।

समाधान के चरण

1. taken := एक नया सेट
2. g1 := n खाली सूचियों वाली सूची
3. g2 := आकार n की सूची और 0 से भरी
4. w := आकार n की सूची और 0 से भरी
5. semester := 0
6. relations में प्रत्येक x के लिए:
   • x[0]-1 को g1[x[1]-1] के अंत में डालें
   • x[1]-1 को g2[x[0]-1] के अंत में डालें
7. weight := g1 में सभी आइटम्स की लंबाई से बनी सूची
8. i को 0 से n-1 तक:
   • g1[i] में प्रत्येक x के लिए:
     • w[x] := max(w[x], weight[i])
9. while len(taken) < n:
   • courses := एक नई सूची
   • i को 0 से n-1 तक:
     • यदि g1[i] खाली है और i taken में नहीं है:
       • (i, w[i]) को courses के अंत में डालें
   • यदि len(courses) > k:
     • courses को दूसरे पैरामीटर के आधार पर रिवर्स ऑर्डर में सॉर्ट करें
     • courses := पहले k कोर्स की सूची
   • semester := semester + 1
   • courses में प्रत्येक x के लिए:
     • g2[x[0]] में प्रत्येक y के लिए:
       • g1[y] से x[0] हटाएं
     • g2[x[0]] := [] (खाली सूची)
     • x[0] को taken में डालें
10. semester वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(n, relations, k):
    taken = set()
    g1 = [[] for _ in range(n)]
    g2 = [[] for _ in range(n)]
    w = [0] * n
    semester = 0
    for x in relations:
        g1[x[1]-1].append(x[0]-1)
        g2[x[0]-1].append(x[1]-1)
    weight = list(map(len, g1))
    for i in range(n):
        for x in g1[i]:
            w[x] = max(w[x], weight[i])
    while len(taken) < n:
        courses = []
        for i in range(n):
            if (not g1[i]) and (i not in taken):
                courses.append([i, w[i]])
        if len(courses) > k:
            courses = sorted(courses, key=lambda x: x[1], reverse=True)
            courses = courses[:k]
        semester += 1
        for x in courses:
            for y in g2[x[0]]:
                g1[y].remove(x[0])
            g2[x[0]] = []
            taken.add(x[0])
    return semester

n = 6
relations = [(1,3),(2,5),(2,4),(5,6)]
k = 2
print(solve(n, relations, k))

इनपुट

6, [(1,3),(2,5),(2,4),(5,6)], 2

आउटपुट

3