Implement a Dependency-Aware Task Scheduler

Implement a TaskManager class with two methods:

• AddTasks(tasks): add one or more tasks into the system.
• ConsumeTask(): return and remove the executable task with the earliest deadline.

Each task has the following fields:

• id: unique task identifier
• ddl: integer deadline, where a smaller value means an earlier deadline
• subTasks: a list of prerequisite task IDs that must be completed before this task can be consumed

Requirements:

1. Support multiple calls to AddTasks.
2. ConsumeTask() should return the pending task with the smallest deadline among all currently executable tasks.
3. A task is executable only if all of its prerequisite tasks have already been consumed.
4. If no executable task exists, return NO_TASK.
5. For this coding problem, assume task IDs are unique and the dependency graph is valid and acyclic.

Explain the data structures you would use and implement both methods efficiently.

Implement a Dependency-Aware Task Scheduler

Design a dependency-aware task scheduler. Each task has an integer id, an integer deadline ddl, and a list subTasks containing prerequisite task IDs. A task can be consumed only after all of its prerequisite tasks have already been consumed.

The original interface is a TaskManager class with:

• AddTasks(tasks): add one or more new tasks
• ConsumeTask(): return and remove the currently executable task with the earliest deadline

For this judge, implement a function solution(operations) that simulates the class.

Each operation is one of:

• ('add', tasks) where tasks is a list of task dictionaries
• ('consume',)

For every ('consume',) operation, append the returned value to the answer list.

Rules:

1. Multiple add operations are allowed.
2. A task is executable only if every ID in subTasks has already been consumed.
3. Among executable tasks, consume the one with the smallest ddl.
4. If several executable tasks have the same ddl, consume the one with the smaller id.
5. If no executable task exists, return 'NO_TASK'.
6. Task IDs are unique, and the dependency graph is valid and acyclic.

Return a list containing the result of every consume operation in order.

Constraints

• 1 <= total number of tasks across all add operations <= 200000
• 0 <= total number of dependency links across all tasks <= 200000
• 0 <= ddl <= 10^9
• Task IDs are unique integers
• The dependency graph is acyclic and all prerequisite IDs are valid task IDs that may appear in earlier or later add operations

Examples

Example 1

Input: [('add', [{'id': 1, 'ddl': 5, 'subTasks': []}, {'id': 2, 'ddl': 3, 'subTasks': []}]), ('consume',), ('consume',), ('consume',)]
Output: [2, 1, 'NO_TASK']

Explanation: Tasks 1 and 2 are immediately executable. Task 2 has the earlier deadline, then task 1, then nothing remains.

Example 2

Input: [('add', [{'id': 1, 'ddl': 5, 'subTasks': []}, {'id': 2, 'ddl': 1, 'subTasks': [1]}, {'id': 3, 'ddl': 4, 'subTasks': []}]), ('consume',), ('consume',), ('consume',), ('consume',)]
Output: [3, 1, 2, 'NO_TASK']

Explanation: Task 2 has the smallest deadline but is blocked by task 1. So task 3 is consumed first, then 1, which unlocks 2.

Hints

1. You need one structure to quickly get the executable task with the smallest deadline, and another structure to update tasks that become executable after a prerequisite is consumed.
2. Track, for each task, how many prerequisites are still unfinished, and keep reverse edges from each prerequisite to the tasks that depend on it.

Approach

This is Kahn's topological-sort algorithm fused with a min-heap so that, among all currently-executable tasks, we always pick the one with the smallest deadline.

State maintained

• tasks: id → {ddl, remaining, consumed} where remaining is the count of not-yet-consumed prerequisites.
• dependents: prereqId → [tasks waiting on it] (a reverse adjacency list).
• consumed: set of already-finished task ids.
• ready: a min-heap of (ddl, id) holding tasks whose prerequisites are all satisfied.

add_tasks — For each new task it scans subTasks. A prerequisite already in consumed is ignored; otherwise it bumps remaining and records this task under that prereq in dependents. This handles out-of-order adds (a task may be added before or after its prerequisite). If remaining == 0, the task is immediately pushed to ready.

consume_task — Pop the smallest (ddl, id). Because the heap key is the tuple (ddl, id), ties on deadline break to the smaller id automatically (rules 3–4). Stale heap entries — already consumed, or whose remaining is no longer 0 — are skipped (lazy deletion). The chosen task is marked consumed; then every dependent's remaining is decremented, and any that reaches 0 is pushed to ready. If the heap empties without a valid task, it returns 'NO_TASK'.

Correctness: A task enters ready exactly when its last outstanding prerequisite is consumed, so rule 2 (all prerequisites done) holds; the heap guarantees the earliest-deadline / smallest-id choice (rules 3–4). Lazy deletion keeps stale tuples harmless.

• Time complexity: O(N log N + E)
• Space complexity: O(N + E)