Deviopath › TypeScript

Build Order with Cycle Detection

Hard · Graphs

deps maps a task name to the tasks it depends on. The set of tasks is every key plus every name that appears in a dependency list (a task that is not a key has no dependencies).

Write buildOrder(deps):

- Repeatedly build the task that is not built yet and whose dependencies are all built. When several tasks are ready, pick the alphabetically smallest one (plain string comparison).

- If every task gets built, return { ok: true, order }.

- Otherwise (there is a cycle), return { ok: false, blocked } where blocked lists all tasks that could not be built, sorted alphabetically.

Next: Find Free Time Slots