Validate and schedule an observable plan

Intermediate65 min

Implement schedule_plan(steps, completed, budget). Validate a dependency graph, then choose currently ready unfinished steps by increasing cost and ID while respecting a shared budget.

Your task

Each step has a unique nonempty string id, a list of dependency IDs, and a positive exact integer cost. Budget is a nonnegative exact integer.
Raise ValueError for duplicate IDs, unknown dependencies, duplicate dependencies, unknown completed IDs, invalid costs, or cycles, even when a cyclic node is marked complete.
A ready step is unfinished and has every dependency in completed. Do not make additional steps ready based on the actions selected in this call.
Sort ready steps by (cost, id), greedily include each that fits the remaining budget, and return the selected IDs. This is a defined heuristic, not a globally optimal scheduler.
Do not mutate steps or completed. Empty valid plans return an empty list.

Examples

EXAMPLE 1

InputA cost 2 and B cost 3 ready; C depends on both; budget 4

Output['A']

Selecting A does not make C ready in the same call.

def schedule_plan(steps, completed, budget):
    raise NotImplementedError