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).

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_id`s 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_id`s** 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.

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_id`s 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_id`s 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]`.