Task Scheduler with Subtasks and Deadline Updates

Problem: Task Scheduler with Subtasks and Deadline Updates Design and implement an online TaskScheduler. Each task has: id: a unique string identifier; deadline: an integer deadline; subtasks: optional list of task ids. When this task is consumed, all of its subtasks should also be marked as consumed. The scheduler supports the following operations. Operations ADD id deadline k sub1 sub2 ... subk Add a task with id id, deadline deadline, and k subtasks. If id has already been consumed, the add fails and outputs None. If id exists but has not been consumed, overwrite its deadline and subtask list, and output OK. Otherwise, add it and output OK. CONSUME Consume the unconsumed task with the smallest deadline. If there is a tie, consume the lexicographically smallest id. Output the consumed task id. Mark this task as consumed. If it has subtasks, mark all direct and indirect subtask ids as consumed as well. Even if a subtask has not been added yet, it is still recorded as consumed and cannot be added or updated later. If no task is available, output None. UPDATE id newDeadline If task id has already been consumed, output None. If task id does not exist, output None. Otherwise, update its deadline to newDeadline and output OK. Input Format The first line contains an integer q, the number of operations. Each of the next q lines is one operation: ADD id deadline k sub1 sub2 ... subk CONSUME UPDATE id newDeadline Output Format Print one line for each operation: ADD / UPDATE: print OK or None; CONSUME: print the consumed task id, or None if no task is available. Constraints 1 <= q <= 2 * 10^5 Task ids and subtask ids are non-empty strings without spaces 0 <= deadline <= 10^9 The total number of subtask references across all operations is at most 2 * 10^5 Example Input: 6 ADD 1 2 0 ADD 2 1 0 CONSUME UPDATE 1 5 CONSUME CONSUME Output: OK OK 2 OK 1 None Example Input 6 ADD 1 2 0 ADD 2 1 0 CONSUME UPDATE 1 5 CONSUME CONSUME Output OK OK 2 OK 1 None