Deviopath › TypeScript

Parallel Task Scheduler

Hard · Modelling

Simulate workers workers running tasks. A task is READY when it has not started yet and all its deps have finished. Dependencies always exist and never form a cycle; durations are positive.

The simulation starts at time 0:

1. While a worker is free and a task is ready, start the ready task with the highest priority (ties: smallest id by string comparison) at the current time.

2. Jump to the next moment a running task finishes, mark every task finishing at that moment as done, and go back to step 1.

Write schedule(tasks, workers) that returns { finishTime, starts }: the time the last task finishes (0 for no tasks) and the start time of every task.

Next: Maze with Keys and Doors