假设我们有一个数字 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))
6, [(1,3),(2,5),(2,4),(5,6)], 2输出结果
3