Is the settlement pipeline schedulable?

Question

A settlement pipeline has n tasks. A dependency (a, b) means task a must run after task b. The pipeline is schedulable only if there is no circular dependency. Decide whether all tasks can be ordered. Return whether a valid ordering exists (no cycle in the dependency graph).

Accepted Answer

Model tasks as a directed graph: (a, b) becomes an edge b - a (b enables a). A valid ordering exists exactly when this graph is acyclic. Run a DFS that colors nodes: white (unvisited), gray (on the current recursion stack), black (finished). Encountering a gray node means a back edge, i.e., a cycle. Tracing the second case: DFS from 0 goes 0 - 1 and then 1 - 0, but 0 is still gray, so it detects a cycle and returns False. Time O(n + edges), space O(n) for colors and recursion. Edge cases: no dependencies is trivially schedulable; disconnected task groups are handled by the outer loop that sta…

Is the settlement pipeline schedulable?

Your answer

More Coding questions