Schedule Ready Tasks by Deadline

Q: Schedule Ready Tasks by Deadline

This question evaluates understanding of task scheduling and dependency management in directed acyclic graphs, along with algorithmic selection and data-structure-based optimization for repeated minimum-deadline retrieval.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are building a workflow scheduler.

Each task has:

a unique task_id
an integer deadline
an optional list of prerequisite tasks that must be completed before this task becomes ready

Assume the dependency graph is a DAG.

Implement the scheduler in three stages:

Basic version : Given a list of tasks with no dependencies, return the task with the smallest deadline.
Dependency-aware version : Tasks may have prerequisites. Repeatedly select the currently ready task with the smallest deadline, mark it as completed, and add any newly unlocked tasks to the ready set. Return a valid execution order.
Optimized version : Improve the time complexity of selecting the next ready task by using an efficient data structure instead of scanning the full ready list each time. Analyze the time complexity.

If multiple ready tasks have the same deadline, you may break ties by task_id or return any consistent order.

Schedule Ready Tasks by Deadline

Quick Overview

Comments (0)