Pythonのすべての異なるコースをカバーするために最小学期を数えるプログラム

番号nがあるとすると、1からnまでのラベルが付けられたn個の異なるコースがあることを示します。また、relations [i]にペア（prevCourse_i、nextCourse_i）が含まれる、relationsという配列もあります。これは、コースprevCourse_iとコースnextCourse_iの間の前提条件の関係を表します。したがって、コースprevCourse_iはコースnextCourse_iの前に取得する必要があります。そして、私たちが持っている最後のパラメータはkです。 1学期では、前の学期に受講しているコースのすべての前提条件を満たしている限り、最大k個のコースを受講できます。すべてのコースを受講するために必要な最小学期数を見つける必要があります。

したがって、入力が次のような場合

最初の学期にコース1と2を受講できるため、出力は3になります。これで、コース3、4、5の資格が得られます。したがって、2学期に5と、3または4のいずれかを受講すると、次のようになります。次の学期にすべてのコースを終了することができます。したがって、合計3学期が必要です

これを解決するには、次の手順に従います-

• 撮影：=新しいセット

• g1：=n個の空のリストを含むリスト

• g2：=サイズnの新しいリストで、0で埋めます

• w：=サイズnの新しいリストで、0で埋めます

• 学期：=0

• 関係の各xについて、実行します

  • g1 [x [1] -1]

    の最後にx[0]-1を挿入します

  • g2 [x [0] -1]

    の最後にx[1]-1を挿入します

• weight：=g1のすべてのアイテムの長さからの新しいリスト

• 0からn-1の範囲のiの場合、実行

  • g1 [i]のxごとに、実行

    • w [x]：=最大w[x]と重み[i]

• 取られたサイズ

  • コース：=新しいリスト

  • 0からn-1の範囲のiの場合、実行

    • g1 [i]が空で、iが取得されていない場合、

      • コースの最後に（i、w [i]）を挿入します

    • コースのサイズがkより大きい場合、

      • コース=2番目のパラメータに基づいてコースを逆の順序で並べ替えます

      • コース：=最初のkコースのリスト

    • 学期：=学期+ 1

    • コースのxごとに、実行します

      • g2 [x [0]]のyごとに、実行

        • g1 [y]

          からx[0]を削除します

      • g2 [x [0]]：=空のリスト

      • x[0]をtakenに挿入

• 学期を返す

例

理解を深めるために、次の実装を見てみましょう

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