title: Finding Minimum Completion Time of Scheduled Tasks with Topological Sort
body: <blockquote>
    <p>Assume that there are an unlimited number of workers each of which can
    complete one task, each of which takes some time. There are also
    precedence constraints where one task cannot be completed until
    another is. What is the minimum amount of time needed for each task to
    be completed while respecting the precedence order?</p>
  </blockquote>
  
  <hr>
  
  <blockquote>
    <p>As an example, lets say you have 3 tasks. </p>
    
    <p>The first task takes 10 units of time to complete, the second takes 5
    units of time to complete, and the third takes 6 units of time to
    complete.</p>
    
    <p>The constraint is that the 2nd task cannot be started until the 3rd
    task is finished.</p>
  </blockquote>
  
  <hr>
  
  <blockquote>
    <p>Given this, you can conclude that the minimum time needed for all the
    tasks to be completed while respecting the precedence is 11.</p>
    
    <p>This is because you can do tasks 1 and 3 (which take times 10 and 6
    respectively) simultaneously, and after task 3 is finished, you can
    begin on task 2 (which takes 5 units of time). Thus, all tasks will
    end at time 11.</p>
  </blockquote>
  
  <hr>
  
  <p>It seems like this could be solved with a topological sort, which would give you the order in which to complete tasks in order to satisfy the constraints.</p>
  
  <p>For example, in the problem, after topologically sorting the tasks you would end up with</p>
  
  <pre><code>Task 1 (10 Units of time) -&gt; Task 3 (6 Units of time) -&gt; Task 2 (5 Units of time)
  </code></pre>
  
  <hr>
  
  <p>However, once you obtain this order in which go about the tasks, how do you determine which ones can be done simultaneously and which ones need to be done one after the other? Further, how do you compute the minimum time needed for all of them to finish?</p>