Nice little graph problem today. I started by creating a Step class which contained references to other steps it depended on. The first part was then solved by looping and flagging steps as completed until all step where completed. Finding the next step to complete simply involved a little LINQ to determine the first (considering a list of steps ordered alphabetically) incomplete step for which all its requirements are completed:
var nextStep = steps.First(s => !s.IsCompleted && s.Requirements.All(r => r.IsCompleted));
For the second part, I thought of multiple possible solutions but ended up doing a simple matrix-like solution similar to the problem description example. This is done by assigning available steps to each idle worker, increasing the time by 1 second and starting over until all steps are completed.
Another possible solution could be to use a priority queue to determine the next completed step, reduce the time for the other running tasks according to the time spent to complete it and start the next task in the queue as long as there are enough workers. This solution could be implemented without creating a Worker class as I did.
Another possible approach could involve have workers push events when their step is completed and have an event handler that would assign him the next available step. This approach is similar to what is done in task scheduling programs, as those used on computing servers for example. As the steps are fictional here, it would involve creating a fictional task to complete (like simply waiting or watching a counter), so it would require a lot more work than the simpler solutions.