পাইথনের বিভিন্ন কোর্স কভার করার জন্য ন্যূনতম সেমিস্টার গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা n আছে, নির্দেশ করে যে 1 থেকে n পর্যন্ত লেবেল করা n বিভিন্ন কোর্স রয়েছে। আমাদের সম্পর্ক নামে একটি অ্যারেও রয়েছে যেখানে সম্পর্ক[i] একটি জোড়া (prevCourse_i, nextCourse_i) ধারণ করে, যা কোর্স prevCourse_i এবং কোর্স nextCourse_i-এর মধ্যে একটি পূর্বশর্ত সম্পর্ককে প্রতিনিধিত্ব করে:তাই কোর্স prevCourse_i কোর্স nextCourse_i এর আগে নিতে হবে। এবং শেষ পরামিতি আমাদের আছে যেটি হল k। একটি সেমিস্টারে, যতক্ষণ পর্যন্ত আমরা যে কোর্সগুলি নিচ্ছি তার জন্য পূর্ববর্তী সেমিস্টারের সমস্ত পূর্বশর্তগুলি গ্রহণ করে থাকি ততক্ষণ পর্যন্ত আমরা সর্বাধিক k সংখ্যক কোর্স নিতে পারি। সমস্ত কোর্স করার জন্য আমাদের ন্যূনতম সেমিস্টারের সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 3 কারণ প্রথম সেমিস্টারে আমরা কোর্স 1 এবং 2 নিতে পারি, এখন আমরা 3, 4 এবং 5 কোর্সের জন্য যোগ্য, তাই আমরা যদি দ্বিতীয় সেমিস্টারের জন্য 5 এবং 3 বা 4 এর যে কোনো একটি নিই, তাহলে আমরা পরের সেমিস্টারে সব কোর্স শেষ করতে পারে। তাই আমাদের মোট ৩টি সেমিস্টার দরকার

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

নেওয়া :=একটি নতুন সেট
g1 :=n খালি তালিকা সহ একটি তালিকা
g2 :=n আকারের একটি নতুন তালিকা এবং 0
দিয়ে পূরণ করুন
w :=আকার n এর একটি নতুন তালিকা এবং 0
দিয়ে পূরণ করুন
সেমিস্টার :=0
প্রতিটি x সম্পর্কের জন্য, করুন
- g1[x[1]-1]
  এর শেষে x[0]-1 ঢোকান
- g2[x[0]-1]
  এর শেষে x[1]-1 ঢোকান
ওজন :=g1
-এ সমস্ত আইটেমের দৈর্ঘ্য থেকে একটি নতুন তালিকা
আমি 0 থেকে n - 1 রেঞ্জের জন্য, করুন
- g1[i]-এ প্রতিটি x এর জন্য করুন
  - w[x] :=সর্বোচ্চ w[x] এবং ওজন[i]
নেওয়ার সময়
- কোর্স :=একটি নতুন তালিকা
- আমি 0 থেকে n - 1 রেঞ্জের জন্য, করুন
  - যদি g1[i] খালি থাকে এবং i নেওয়া না হয়, তাহলে
    - কোর্সের শেষে সন্নিবেশ করুন (i, w[i])
  - যদি কোর্সের আকার> k, তাহলে
    - কোর্স =বিপরীত ক্রমে দ্বিতীয় প্যারামিটারের উপর ভিত্তি করে কোর্সগুলি সাজান
    - কোর্স :=প্রথম কে কোর্সের তালিকা
  - সেমিস্টার :=সেমিস্টার + 1
  - প্রতিটি x কোর্সের জন্য, করুন
    - g2[x[0]]-এ প্রতিটি y-এর জন্য করুন
      - g1[y]
        থেকে x[0] মুছে দিন
    - g2[x[0]] :=খালি তালিকা
    - নেওয়ার মধ্যে x[0] ঢোকান
রিটার্ন সেমিস্টার

উদাহরণ

আরও ভালোভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি

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