ETL pipelines consist of tasks with dependencies between them, forming a directed acyclic graph (DAG). An orchestrator must schedule tasks so that dependencies are respected, while utilizing available resources efficiently through parallel execution.
Given a set of tasks with durations, resource costs, and dependency lists, produce a schedule that assigns a start time to each task.
At each point in time:
Complete any tasks whose end time has been reached
Identify ready tasks: all dependencies completed, not yet started or running
Sort ready tasks alphabetically by name
Greedily assign tasks in that order, skipping any that would exceed the resource budget (sum of resources of all currently running tasks + new task must not exceed budget)
Advance time to the next task completion event
Return a list of tuples (task_name, start_time) sorted by (start_time, task_name).
Input:
tasks = [ {"name": "extract", "duration": 2, "resources": 1, "depends_on": []}, {"name": "transform", "duration": 3, "resources": 1, "depends_on": ["extract"]}, {"name": "load", "duration": 1, "resources": 1, "depends_on": ["transform"]}, ] resource_budget = 2
Output:
[("extract", 0), ("transform", 2), ("load", 5)]
Linear chain: each task waits for the previous one to finish.
Input:
tasks = [ {"name": "fetch_orders", "duration": 3, "resources": 1, "depends_on": []}, {"name": "fetch_users", "duration": 2, "resources": 1, "depends_on": []}, {"name": "join", "duration": 1, "resources": 2, "depends_on": ["fetch_users", "fetch_orders"]}, ] resource_budget = 2
Output:
[("fetch_orders", 0), ("fetch_users", 0), ("join", 3)]
Both fetch tasks run in parallel (1+1=2 <= budget). Join starts after the slower one (fetch_orders) finishes at time 3.
Track running tasks with their end times. At each step, complete all tasks whose end time has been reached.
A task that does not fit the current resource budget is skipped, but later tasks in the ready queue might still fit.
Sign in to take notes on this problem
Accepts: array
Accepts: number
ETL pipelines consist of tasks with dependencies between them, forming a directed acyclic graph (DAG). An orchestrator must schedule tasks so that dependencies are respected, while utilizing available resources efficiently through parallel execution.
Given a set of tasks with durations, resource costs, and dependency lists, produce a schedule that assigns a start time to each task.
At each point in time:
Complete any tasks whose end time has been reached
Identify ready tasks: all dependencies completed, not yet started or running
Sort ready tasks alphabetically by name
Greedily assign tasks in that order, skipping any that would exceed the resource budget (sum of resources of all currently running tasks + new task must not exceed budget)
Advance time to the next task completion event
Return a list of tuples (task_name, start_time) sorted by (start_time, task_name).
Input:
tasks = [ {"name": "extract", "duration": 2, "resources": 1, "depends_on": []}, {"name": "transform", "duration": 3, "resources": 1, "depends_on": ["extract"]}, {"name": "load", "duration": 1, "resources": 1, "depends_on": ["transform"]}, ] resource_budget = 2
Output:
[("extract", 0), ("transform", 2), ("load", 5)]
Linear chain: each task waits for the previous one to finish.
Input:
tasks = [ {"name": "fetch_orders", "duration": 3, "resources": 1, "depends_on": []}, {"name": "fetch_users", "duration": 2, "resources": 1, "depends_on": []}, {"name": "join", "duration": 1, "resources": 2, "depends_on": ["fetch_users", "fetch_orders"]}, ] resource_budget = 2
Output:
[("fetch_orders", 0), ("fetch_users", 0), ("join", 3)]
Both fetch tasks run in parallel (1+1=2 <= budget). Join starts after the slower one (fetch_orders) finishes at time 3.
Track running tasks with their end times. At each step, complete all tasks whose end time has been reached.
A task that does not fit the current resource budget is skipped, but later tasks in the ready queue might still fit.
Sign in to take notes on this problem
Accepts: array
Accepts: number