Service Startup Planner
Asked at Snowflake· Screen
Reported by the problem's creator, not verified
You are planning the startup of n services numbered 0 to n - 1. A service can only start after every service it requires has started. ServiceGraph(n) begins with no requirements; requirements are added one at a time, and the plan is queried as calls arrive.
Examples
Example 1
Input: init =
[5], operations =[["add_dependency",[0,3]],["add_dependency",[3,0]],["add_dependency",[4,2]],["add_dependency",[0,3]],["start_order",[]]]Output:
[true,false,true,true,[1,2,3,0,4]]Explanation: The edge
3requires0would close a cycle with0requires3, so it is rejected; the repeated0requires3is accepted. Services 1, 2 and 3 are ready first: 1 starts, then 2, then 3, which unblocks 0. Service 4 (waiting on 2) is also ready, but 0 is smaller, giving [1, 2, 3, 0, 4].