使用Python计算最少需要多少学期才能完成所有不同课程的程序

假设我们有一个数字n，表示有n门不同的课程，从1到n进行标记。我们还有一个被称为关系的数组，其中relations[i]包含一对(prevCourse_i, nextCourse_i)，代表先决关系在课程prevCourse_i和课程nextCourse_i之间：因此，在进行课程nextCourse_i之前，必须先进行课程prevCourse_i。我们还有一个最后的参数k。在一个学期内，我们最多可以修读k门课程，只要我们已经修完以前学期中课程的所有先决条件。现在我们需要找到修完所有课程所需的最少学期数。

所以，如果输入是这样的：

那么输出将会是3，因为在第一学期，我们可以修读课程1和2，现在我们有资格修读课程3、4和5，如果我们在第二学期修读课程5和3或4中的任何一个，那么我们就可以在下一个学期完成所有课程。因此，我们需要总共3个学期。

要解决这个问题，我们将遵循以下步骤 –

taken := 新集合
g1 := n个空列表的列表
g2 := 大小为n的新列表，填充为0
w := 大小为n的新列表，填充为0
semester := 0
对于每个x在关系中，做：
- 将x[0] – 1插入到g1[x[1] – 1]的结尾
- 将x[1] – 1插入到g2[x[0] – 1]的结尾
weight := 所有g1中所有项的长度的新列表
对于i在0到n-1的范围中，做：
- 对于g1[i]中的每个x，做：
  - w[x] := w[x]和weight[i]中的最大值
当taken集合大小＜n时，做：
- courses := 新列表
- 对于i在0到n-1的范围内，做：
  - 如果g1[i]为空且i不在taken中，则：
  - 将(i，w[i])插入到courses的结尾处
  - 如果courses的大小> k，则
  - 以第二个参数为基础将courses按逆序排序
  - courses := 前k门课程的列表
  - semester := semester + 1
  - 对于courses中的每个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))