goovie's blog

By goovie, history, 6 weeks ago, In English,

Hello. Some time ago I encountered a problem:

You are given DAG (directed acyclic graph) of tasks and an array that describes how much time each task takes to be executed. Graph describes dependencies between tasks. If there is an edge from a to b, it means that in order to start executing task a, task b has to finish execution. Now the question is: given some task c and k processors, what is the earliest time c can finish execution?

This problem is easy when we have only 1 processor or infinite amount of processors, but when we restrict ourselves to k processors the question becomes harder. I think I have some idea about this problem, but in order to make sure I'd like to code the solution. Does anyone know online judge that has this problem?

  • Vote: I like it  
  • +9
  • Vote: I do not like it  

6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone? :P