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

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告