Python 并行课程

假设有 N 门课程，编号从 1 到 N。我们还有一个关系数组 relations，其中 relations[i] = [X, Y] 表示课程 X 和课程 Y 之间的先修关系。这意味着必须先学习课程 X，才能学习课程 Y。

在一个学期中，我们可以学习任意数量的课程，只要我们已经学习了我们正在学习的课程的所有先修课程。我们必须找到学习所有课程所需的最小学期数。如果无法学习所有课程，则返回 -1。

例如，如果输入为 N = 3，relations = [[1,3],[2,3]]，则输出为 2，因为在第一学期学习课程 1 和 2，在第二学期学习课程 3。

为了解决这个问题，我们将遵循以下步骤：

  • courses := n

  • visited := 一个大小为 n+1 的数组，并将其全部填充为 false

  • queue := 一个新的列表

  • graph := 一个包含 n+1 个子列表的列表

  • in_degree := 一个大小为 n+1 的数组，并将其全部填充为 0

  • 对于 relations 中的每个 i，执行：

    • 将 i[1] 插入到 graph[i[0]] 的末尾

    • in_degree[i[1]] := in_degree[i[1]] + 1

  • semester := 1

  • 对于范围 1 到 n+1 中的每个 i，执行：

    • 如果 in_degree[i] 为零，则

      • 将 i 插入到 queue 的末尾

      • visited[i] := True

  • semester := 1

  • courses := courses - queue 的大小

  • 当 queue 不为空且 courses 不为零时，执行：

    • current_size := queue 的大小

    • 当 current_size 不为零时，执行：

      • current_course := queue[0]

      • 从 queue 中删除第一个元素

      • current_size := current_size - 1

      • 对于 graph[current_course] 中的每个 i，执行：

        • in_degree[i] := in_degree[i] - 1

        • 如果 i 未被访问且 in_degree[i] 为零，则

          • courses := courses - 1

          • 将 i 插入到 queue 的末尾

          • visited[i]:= True

    • semester := semester + 1

  • 如果 courses 为 0，则返回 semester，否则返回 -1

让我们来看下面的实现，以便更好地理解：

示例

 在线演示

class Solution(object):
   def minimumSemesters(self, n, relations):
      courses = n
      visited = [False for i in range(n+1)]
      queue = []
      graph = [[] for i in range(n+1)]
      in_degree = [0 for i in range(n+1)]
      for i in relations:
         graph[i[0]].append(i[1])
         in_degree[i[1]]+=1
      semeseter = 1
      for i in range(1,n+1):
         if not in_degree[i]:
            queue.append(i)
            visited[i] = True
         semester = 1
         courses -= len(queue)
         while queue and courses:
            current_size = len(queue)
            while current_size:
               current_course = queue[0]
               queue.pop(0)
               current_size-=1
               for i in graph[current_course]:
                  in_degree[i]-=1
                  if not visited[i] and not in_degree[i]:
                     courses-=1
                     queue.append(i)
                  visited[i]=True
            semester+=1
         return semester if not courses else -1

ob = Solution()
print(ob.minimumSemesters(3,[[1,3],[2,3]]))

输入

3, [[1,3],[2,3]]

输出

-1

更新于：2020年7月11日

浏览量：191

开启你的职业生涯

完成课程获得认证

开始学习
广告