计算最小学期以涵盖 Python 中所有不同课程的程序

Z时代
2024-01-10
分类：综合

假设我们有一个数字 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 中的任何一个，那么我们可以在下学期结束所有课程。所以我们总共需要3个学期

示例

让我们看看以下实现以更好地理解

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))