Schedule Ready Tasks by Deadline

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:

1. Basic version: Given a list of tasks with no dependencies, return the task with the smallest deadline.
2. 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.
3. 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.

Part 1: Earliest Deadline Task Without Dependencies

Find the task with the earliest deadline from a list of independent tasks (no dependencies).

What to implement

Implement solution(tasks).

• Input: tasks — a list of (task_id, deadline) pairs (each pair is a 2-tuple of integers).
• Output: the task_id (an integer) of the task with the smallest deadline, or None if the list is empty.

Rules

1. Return the task_id whose deadline is the smallest.
2. Tie-break: if two or more tasks share the same smallest deadline, return the one with the smaller task_id, so the answer is deterministic.
3. If tasks is empty, return None.

Examples

• [(101, 5), (102, 2), (103, 8)] → 102 — deadline 2 is the smallest.
• [(3, 4), (1, 4), (2, 6)] → 1 — tasks 3 and 1 both have deadline 4; the smaller task_id (1) wins.
• [(7, 10)] → 7 — only one task.
• [] → None — empty input.

Constraints

• 0 <= len(tasks) <= 100000
• task_id values are unique integers.
• deadline is an integer in the range [-10^9, 10^9] (deadlines may be negative).

Hints

1. A full sort is unnecessary; you only need to track the best task seen so far.
2. Decide how to handle ties before you start scanning.

Approach

Approach: single-pass linear scan with a tie-break.

We need the task_id whose deadline is smallest, breaking ties toward the smaller task_id. A full sort is unnecessary — finding a minimum only requires one pass.

Steps:

• Empty guard: if tasks is empty, return None immediately (the problem's required base case).
• Seed: initialize best_id, best_deadline from tasks[0]. Seeding from a real element avoids needing a sentinel like +infinity and keeps the comparison logic uniform.
• Scan the rest: for each remaining (task_id, deadline), replace the current best when either:
  • deadline < best_deadline (a strictly earlier deadline always wins), or
  • deadline == best_deadline and task_id < best_id (same deadline, but this id is smaller).

Why it's correct: the loop maintains the invariant that (best_id, best_deadline) is the answer for everything seen so far, ordered first by deadline ascending, then by id ascending. Each new task is compared against that running best under exactly the same ordering, so after the final element the invariant holds over the whole list. The tie-break uses strict < on task_id, so an equal id never displaces itself, and since ids are unique the result is deterministic.

Edge cases handled: a single-element list returns that task's id directly; negative deadlines work because comparisons are plain integer <; the empty list returns None. Note the loop slices tasks[1:], which is a clean way to skip the already-seeded first element.

• Time complexity: O(n)
• Space complexity: O(1)

Part 2: Schedule Ready Tasks by Deadline

Schedule a set of tasks that have deadlines and prerequisite dependencies, always running the most urgent task that is currently allowed to run.

What to implement

Implement a function solution(tasks) that returns the order in which the tasks are executed, as a list of task_id values.

Input

tasks is a list of triples, one per task:

(task_id, deadline, prerequisites)

• task_id — a unique integer identifying the task.
• deadline — an integer; smaller means more urgent.
• prerequisites — a list of task_ids that must be completed before this task may run.

The dependency graph is guaranteed to be a DAG (no cycles). Every ID that appears in any prerequisites list also appears as a task in tasks.

Output

Return a list of task_ids giving the full execution order (every task appears exactly once).

If tasks is empty, return an empty list [].

Rules

A task is ready when all of its prerequisites have already been completed. A task with no prerequisites is ready from the start.

Process tasks one at a time:

1. Look at the set of currently ready tasks.
2. Choose the ready task with the smallest deadline.
3. Tie-break: if several ready tasks share the smallest deadline, choose the one with the smallest task_id.
4. Complete that task: append its task_id to the output order, then unlock any task whose prerequisites are now all completed (those tasks become ready).
5. Repeat until every task has been scheduled.

Use a simple ready-list approach: each step, scan the current set of ready tasks to find the next task to run by the rules above.

Example

tasks = [(1, 4, []), (2, 2, []), (3, 3, [1, 2]), (4, 1, [2])]
solution(tasks) -> [2, 4, 1, 3]

• Initially ready: tasks 1 (deadline 4) and 2 (deadline 2). Pick 2 (smaller deadline).
• Completing 2 unlocks 4. Ready: 1 (deadline 4) and 4 (deadline 1). Pick 4.
• Ready: 1. Pick 1, which unlocks 3.
• Ready: 3. Pick 3. Final order: [2, 4, 1, 3].

Constraints

• 0 <= number of tasks <= 3000
• 0 <= total number of prerequisite references <= 20000
• task_id values are unique integers.
• Every prerequisite ID appears in the task list.
• The dependency graph is a DAG.

Hints

1. Track how many prerequisites each task still needs; this is often called an indegree count.
2. Keep a list of currently ready tasks, and linearly scan that list to find the next task to run.

Approach

This is a deadline-greedy topological sort over a DAG, using a simple ready-list that is rescanned each step.

Setup. We walk the task list once to record each task's deadline, its indegree (number of prerequisites, taken directly as len(prereqs)), and seed an empty adjacency list in graph. A second pass builds the edges: for every prereq pre of a task, we append the task to graph[pre], so graph maps prerequisite → dependents. Edges always point from a completed task to the tasks it unlocks.

Scheduling loop. ready starts with every task whose indegree == 0 (no prerequisites). While ready is non-empty:

• We linearly scan ready to pick the best candidate — smallest deadline, breaking ties by smaller task_id (deadline[a] < deadline[b] or (deadline[a] == deadline[b] and a < b)).
• We pop that task from ready, append it to order, then for each dependent nxt in graph[task_id] we decrement indegree[nxt]. When a dependent's indegree hits 0, all its prerequisites are done, so we push it onto ready.

Why it's correct. A task only becomes ready after every prerequisite is completed (indegree reaches 0), so prerequisite ordering is always respected. Among currently-eligible tasks, the explicit min-scan enforces the exact tie-break rule (deadline, then id). Because the input is a guaranteed DAG, every task eventually reaches indegree 0, so all n tasks are scheduled. The final len(order) != len(tasks) check is a safety guard (would catch a cycle), and the empty-input case returns [] early.

• Time complexity: O(n^2 + m), where n is the number of tasks and m is the total prerequisite references. The while loop runs n times, and each iteration linearly scans the ready list (up to O(n)), giving O(n^2); building the graph and decrementing indegrees over all edges contributes O(m).
• Space complexity: O(n + m): the deadline, indegree, and ready structures hold O(n) entries, while the adjacency lists in graph store O(m) edges in total.

Part 3: Optimized Deadline-Aware Task Scheduler

Schedule a set of tasks that have deadlines and prerequisite dependencies, always running the most urgent task that is currently runnable, and return the order in which the tasks execute.

This is the optimized version of the scheduler: instead of scanning the entire list of runnable tasks on every step to find the next one, you must use an efficient data structure (such as a min-heap / priority queue) to retrieve the next task in logarithmic time.

Function

def solution(tasks):

Input

tasks is a list of tasks. Each task is a tuple:

(task_id, deadline, prerequisites)

• task_id — a unique integer identifying the task.
• deadline — an integer; smaller means more urgent.
• prerequisites — a list of task_ids that must all be completed before this task can run. An empty list means the task has no prerequisites.

The prerequisite relationships form a DAG (directed acyclic graph), so there are no circular dependencies. Every task_id referenced as a prerequisite also appears as a task in the list.

Rules

1. A task is ready (runnable) once all of its prerequisite tasks have been completed. A task with no prerequisites is ready from the start.
2. At each step, among all currently ready tasks, execute the one with the smallest deadline. If two ready tasks share the same deadline, execute the one with the smaller task_id.
3. Completing a task may make other tasks ready (when it was their last unmet prerequisite); those tasks then join the pool of ready tasks for future steps.
4. Continue until all tasks have been executed.

Output

Return a list of task_ids giving the full execution order in which the tasks were run.

Edge cases

• If tasks is empty, return an empty list [].
• A single task with no prerequisites simply produces a one-element list containing its task_id.

Example

Given tasks = [(1, 4, []), (2, 2, []), (3, 3, [1, 2]), (4, 1, [2])]:

• Initially ready: tasks 1 (deadline 4) and 2 (deadline 2). Run 2 (smaller deadline).
• Completing 2 makes 4 ready (deadline 1). Now ready: 1 (4), 4 (1). Run 4.
• Run 1 (4). Completing 1 makes 3 ready (its other prerequisite 2 is already done).
• Run 3.

The execution order is [2, 4, 1, 3].

Constraints

• 0 <= number of tasks <= 100000
• 0 <= total number of prerequisite references <= 200000
• task_id values are unique integers
• Every prerequisite ID appears in the task list
• The dependency graph is a DAG

Hints

1. A min-heap is a natural way to repeatedly retrieve the smallest ready task.
2. You still need the same graph bookkeeping as before: indegrees and edges from each prerequisite to the tasks it unlocks.

Approach

This is Kahn's topological sort driven by a min-heap instead of a FIFO queue, which gives the required deadline-aware ordering efficiently.

Setup. Three maps are built from the task list:

• deadline[task_id] — each task's deadline.
• indegree[task_id] — number of prerequisites (the count of incoming edges).
• graph[pre] — adjacency list mapping a prerequisite to the tasks that depend on it.

The first loop records deadlines, indegrees, and an empty adjacency entry per task. The second loop fills graph: for every task_id with prerequisite pre, it appends task_id to graph[pre], so an edge points from prerequisite to dependent.

Selection. All tasks with indegree == 0 (no prerequisites) are pushed onto a heap as (deadline, task_id) tuples. Python's heapq orders by deadline first, then task_id, which exactly matches the rule "smallest deadline, ties broken by smaller task_id."

Main loop. Repeatedly pop the minimum tuple, append its task_id to order, then relax its outgoing edges: each dependent's indegree is decremented, and any dependent that reaches 0 becomes ready and is pushed. The heap always holds exactly the currently-ready tasks, so we never scan a full ready list — that is the optimization over the naive version.

Correctness. A task is emitted only after every prerequisite is popped (indegree hits 0), so all dependency constraints hold. Among ready tasks the heap guarantees the globally smallest (deadline, task_id) is chosen. The final len(order) != len(tasks) check would catch a cycle (returning []); for the guaranteed DAG it always passes. Empty input short-circuits to [].

• Time complexity: O(n log n + m)
• Space complexity: O(n + m)