Schedule ETL tasks that form a dependency graph under a shared resource budget. Each task has a unique name, positive integer duration, resource requirement, and depends_on list.
At each time value, first complete every running task whose end time has been reached. Next, collect unscheduled tasks whose dependencies are complete, sort them alphabetically, and greedily start each task that fits the remaining resource budget. Skipped tasks may start at a later completion event. Advance time to the next running-task completion.
Return a list of {"task_name": str, "start_time": int} dictionaries sorted by start time and then 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: [{"task_name": "extract", "start_time": 0}, {"task_name": "transform", "start_time": 2}, {"task_name": "load", "start_time": 5}]
Explanation: Each task starts when its preceding dependency finishes.
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: [{"task_name": "fetch_orders", "start_time": 0}, {"task_name": "fetch_users", "start_time": 0}, {"task_name": "join", "start_time": 3}]
Track running tasks as {name: end_time} and advance to min(running.values()).
After completions, sort ready task dictionaries with key=lambda task: task["name"].
Sign in to take notes on this problem
Accepts: array
Accepts: number
Schedule ETL tasks that form a dependency graph under a shared resource budget. Each task has a unique name, positive integer duration, resource requirement, and depends_on list.
At each time value, first complete every running task whose end time has been reached. Next, collect unscheduled tasks whose dependencies are complete, sort them alphabetically, and greedily start each task that fits the remaining resource budget. Skipped tasks may start at a later completion event. Advance time to the next running-task completion.
Return a list of {"task_name": str, "start_time": int} dictionaries sorted by start time and then 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: [{"task_name": "extract", "start_time": 0}, {"task_name": "transform", "start_time": 2}, {"task_name": "load", "start_time": 5}]
Explanation: Each task starts when its preceding dependency finishes.
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: [{"task_name": "fetch_orders", "start_time": 0}, {"task_name": "fetch_users", "start_time": 0}, {"task_name": "join", "start_time": 3}]
Track running tasks as {name: end_time} and advance to min(running.values()).
After completions, sort ready task dictionaries with key=lambda task: task["name"].
Sign in to take notes on this problem
Accepts: array
Accepts: number