具有依赖性的进程调度算法，（线性时间）

Question

我在尝试弄清楚如何创建一个算法来创建一个时间表以最大限度地减少所用的最小时间时遇到了一些麻烦。问题就在这里。

考虑一个具有进程 1,2,3,4...n 的程序。所有进程都必须完成才能使程序运行，并且某些进程可能依赖于另一个进程来完成。 （例如，流程 2 依赖于流程 1，这意味着我们必须在开始流程 2 之前完成流程 1）

我们拥有无限数量的机器，以便进程可以并行运行

所有流程需要相同的时间完成

设计一种算法，以使用最短的时间来运行程序，并将所有进程的依赖项列表作为输入。

感谢您的帮助！

所以我想要制作这个算法的方法是将问题视为 DAG（有向无环图），然后使用拓扑排序来创建完成任务的顺序，但是，我对如何找到最快的解决方案感到困惑.

例如，假设我们有：

A 不依赖任何东西\
B 依赖于 A \
C 依赖于 A \
D 依赖于 C \
E 不依赖任何东西\
F 依赖于 B、D、E \

如果每个进程需要 1 秒完成，并且我们可以使用无限的机器并行处理它们，那么我们可以在 4 秒内完成程序，对吧？

但是我如何创建一个算法来找出 4 秒是最小的数字？

抱歉，如果我没能清楚地解释问题，

Answer 1

由于我们拥有无限数量的机器，因此一旦可以处理任务，最好分配一台新机器来执行它。所以我们可以根据这个观察结果做一个贪心算法：

Let ToDo be an empty queue
Let time = 0

For every node u :
   If u has no dependency :
      Add (u, 1) at the end of the ToDo
  
While ToDo is not empty :
   Let (u, t) be the head of ToDo
   Let time = max(time, t)
   For all nodes v depending on u :
         If u was the only dependency of v :
            Add (v, t+1) to the end of ToDo
   Remove u from the graph //(Hence no node depend on u anymore)

Return time

Answer 2

构建一个依赖关系图，其中进程的条目将包含依赖于该进程的进程列表。还为所有进程创建一个度数数组，用于计算进程所依赖的进程数。遍历度数数组并将度数为 0 的进程添加到队列中。现在编写一个 while 循环，该循环将在队列计数大于 0 时运行。在每个循环中 deque 一个进程，并从图中获取依赖于该进程的进程，该进程将其度数减 1，如果度数变为 0，则将该进程添加到队列中。 https://leetcode.com/problems/course-schedule/

https://leetcode.com/problems/course-schedule/submissions/1228251959/