Implement multi-level task manager APIs

You are implementing an in-memory task management system with a set of APIs that evolve over 4 levels. All APIs receive a timestamp: int parameter. Unless otherwise stated, timestamps are integers and can be assumed to be non-decreasing across calls (you may state and rely on this if needed).

Task IDs are generated sequentially as strings:

• First task is "task_id_1", then "task_id_2", etc.
• Creation order is the numeric suffix order (e.g., task_id_2 comes before task_id_10).

A task has:

• name: str
• priority: int (non-negative, >= 0)

Assignments (introduced later) are time-based.

---

Level 1: Basic task CRUD

Implement the following:

1. add_task(self, timestamp: int, name: str, priority: int) -> str

   • Adds a new task with the given name and priority.
   • Returns the unique task ID.
   • Adding multiple tasks with the same name and priority is allowed; tasks are differentiated by ID.
   • Note: timestamp is unused in Level 1 logic; included for API consistency.

2. update_task(self, timestamp: int, task_id: str, name: str, priority: int) -> bool

   • Updates the name and priority of the task identified by task_id.
   • Returns True if update succeeds; False if task_id does not exist.

3. get_task(self, timestamp: int, task_id: str) -> str | None

   • Retrieves a task by task_id.
   • If it exists, return a JSON-formatted string containing the task details (name and priority).
   • If it does not exist, return None.

---

Level 2: Searching and sorting tasks

Add the following APIs:

1. search_tasks(self, timestamp: int, name_filter: str, max_results: int) -> list[str]

   • Finds tasks whose name contains name_filter as a case-sensitive substring.
   • Returns up to max_results matching task IDs.
   • Sort results by:
     1. priority descending, then
     2. creation order ascending.
   • If max_results <= 0, return [].

2. list_tasks_sorted(self, timestamp: int, limit: int) -> list[str]

   • Returns up to limit task IDs across the system.
   • Sorting is the same: priority descending, then creation order ascending.

---

Level 3: Users and time-based task assignments

Introduce users with quotas and time-windowed assignments.

1. add_user(self, timestamp: int, user_id: str, quota: int) -> bool

   • Adds a new user with a maximum number of simultaneously active assignments (quota).
   • Returns True if added, False if user_id already exists.

2. assign_task(self, timestamp: int, task_id: str, user_id: str, finish_time: int) -> bool

   • Assigns task_id to user_id for the time interval [timestamp, finish_time).
   • The assignment is active at time t iff start_time <= t < finish_time.
   • Returns True if successful; otherwise False if:
     • the task does not exist, or
     • the user does not exist, or
     • the user's quota is already fully used by currently active assignments.
   • Each successful active assignment consumes one quota slot while it remains active.

3. get_user_tasks(self, timestamp: int, user_id: str) -> list[str]

   • Returns all active task IDs assigned to user_id at the given timestamp.
   • Only include assignments where start_time <= timestamp < finish_time.

---

Level 4: Completion and overdue detection

Add completion and overdue queries.

1. complete_task(self, timestamp: int, task_id: str, user_id: str) -> bool

   • Marks a task as completed by user_id at time timestamp.
   • The task must be assigned to the user and active at timestamp.
   • When completed, the user's quota slot is freed immediately.
   • Returns True if successful; otherwise False if:
     • task does not exist, or
     • user does not exist, or
     • task is not assigned to the user at timestamp.

2. get_overdue_assignments(self, timestamp: int, user_id: str) -> list[str]

   • Returns task IDs for assignments that were given to user_id and expired without completion.
   • An assignment is overdue if:
     • finish_time <= timestamp, and
     • the task was not completed before the finish_time of that specific assignment.

---

Implement the full system so that all levels work together consistently. Clarify any additional assumptions you need (e.g., whether timestamps are non-decreasing, whether a task can be assigned multiple times, and how repeated assignments to the same user/task should behave), but your behavior must remain consistent with the definitions above.

Part 1: Task CRUD Simulator

Simulate a small in-memory task manager. Each new task gets an ID in creation order: task_id_1, task_id_2, and so on. Process a list of operations and return the output for each operation in order. Supported operations are add, update, and get. For a get operation, return a compact JSON string with keys in this exact order: name, then priority. If a task does not exist, return None.

Constraints

• 0 <= len(operations) <= 10000
• Timestamps are non-decreasing, but they do not affect Level 1 behavior
• 0 <= priority <= 10^9
• Task IDs must be generated exactly as task_id_1, task_id_2, ...

Examples

Example 1

Input: [('add', 1, 'write', 3), ('get', 2, 'task_id_1'), ('update', 3, 'task_id_1', 'write docs', 5), ('get', 4, 'task_id_1')]
Output: ['task_id_1', '{"name":"write","priority":3}', True, '{"name":"write docs","priority":5}']

Explanation: Create one task, read it, update it, then read the updated version.

Example 2

Input: [('add', 1, 'bug', 1), ('add', 2, 'bug', 1), ('get', 3, 'task_id_2')]
Output: ['task_id_1', 'task_id_2', '{"name":"bug","priority":1}']

Explanation: Tasks with identical fields are still different because IDs are unique.

Hints

1. Use a dictionary keyed by task_id so update and get are O(1).
2. Keep a counter for the next numeric suffix, and use a JSON serializer to produce the exact string format.

Part 2: Search and Sort Tasks

Build a task catalog that supports insertion, substring search, and global listing. Every added task gets an ID in creation order. A search matches tasks whose name contains the filter as a case-sensitive substring. Search results and global listings must be sorted by priority descending, then by creation order ascending. Process all operations and return the result of each one.

Constraints

• 0 <= len(operations) <= 2000
• 0 <= priority <= 10^9
• Timestamps are non-decreasing, but they do not affect sorting logic here
• Substring matching is case-sensitive
• Sorting rule: higher priority first, then earlier creation first

Examples

Example 1

Input: [('add', 1, 'alpha', 5), ('add', 2, 'beta', 2), ('add', 3, 'alphabet', 5), ('search', 4, 'alpha', 5), ('list', 5, 2)]
Output: ['task_id_1', 'task_id_2', 'task_id_3', ['task_id_1', 'task_id_3'], ['task_id_1', 'task_id_3']]

Explanation: Both matching tasks have priority 5, so creation order breaks the tie.

Example 2

Input: [('add', 1, 'Task', 4), ('add', 2, 'task', 4), ('search', 3, 'Task', 10), ('search', 4, 'task', 10)]
Output: ['task_id_1', 'task_id_2', ['task_id_1'], ['task_id_2']]

Explanation: Search is case-sensitive.

Hints

1. Store a creation index when each task is added.
2. A sort key like (-priority, creation_index) directly matches the required order.

Part 3: Users and Time-Windowed Assignments

Extend the task manager with users and time-based assignments. Each assignment created at time t with finish_time f is active on the half-open interval [t, f). A user has a quota: the maximum number of simultaneously active assignments. Process the operations and return the output of each one. For get_user_tasks, return all active task IDs for that user in assignment creation order. If the same task is assigned multiple times and multiple assignments are active, duplicate task IDs may appear. If get_user_tasks is called for an unknown user, return an empty list.

Constraints

• 0 <= len(operations) <= 2000
• Timestamps are non-decreasing
• 0 <= priority <= 10^9
• 0 <= quota <= 10^9
• Every assign operation satisfies finish_time > t

Examples

Example 1

Input: [('add_task', 0, 'A', 1), ('add_task', 1, 'B', 2), ('add_user', 2, 'alice', 1), ('assign', 3, 'task_id_1', 'alice', 10), ('assign', 4, 'task_id_2', 'alice', 8), ('get_user_tasks', 5, 'alice'), ('get_user_tasks', 10, 'alice')]
Output: ['task_id_1', 'task_id_2', True, True, False, ['task_id_1'], []]

Explanation: Alice's quota is 1, so the second assignment fails while the first one is still active. The interval is half-open, so the task is not active at time 10.

Example 2

Input: [('add_task', 0, 'A', 1), ('add_task', 1, 'B', 1), ('add_user', 2, 'u', 1), ('assign', 2, 'task_id_1', 'u', 3), ('assign', 3, 'task_id_2', 'u', 6), ('get_user_tasks', 3, 'u')]
Output: ['task_id_1', 'task_id_2', True, True, True, ['task_id_2']]

Explanation: At time 3, the first assignment has already expired, so quota is available for the second one.

Hints

1. To check whether an assignment fits, count how many assignments for that user satisfy start <= t < finish at the assignment timestamp.
2. If you store assignment records in insertion order, you can scan them later to build get_user_tasks in the required order.

Part 4: Task Completion and Overdue Detection

Add completion and overdue queries to the task assignment system. Each assignment is its own record. An assignment is active at time t if start <= t < finish and it has not been completed before or at t. Completing a task frees the quota slot immediately, so later operations at the same timestamp should see that slot as available. For deterministic behavior, if multiple active assignments exist for the same task_id and user_id, complete the earliest such assignment. The overdue query returns one task ID per overdue assignment in assignment creation order; duplicates are allowed. If overdue is called for an unknown user, return an empty list.

Constraints

• 0 <= len(operations) <= 2000
• Timestamps are non-decreasing
• 0 <= priority <= 10^9
• 0 <= quota <= 10^9
• Every assign operation satisfies finish_time > t

Examples

Example 1

Input: [('add_task', 0, 'A', 1), ('add_task', 1, 'B', 2), ('add_user', 1, 'alice', 1), ('assign', 2, 'task_id_1', 'alice', 5), ('complete', 3, 'task_id_1', 'alice'), ('assign', 3, 'task_id_2', 'alice', 6), ('overdue', 10, 'alice')]
Output: ['task_id_1', 'task_id_2', True, True, True, True, ['task_id_2']]

Explanation: Completing task_id_1 at time 3 frees Alice's only slot immediately, so task_id_2 can be assigned at the same timestamp. The second task later becomes overdue.

Example 2

Input: [('add_task', 0, 'A', 1), ('add_user', 0, 'u', 1), ('assign', 1, 'task_id_1', 'u', 4), ('complete', 4, 'task_id_1', 'u'), ('overdue', 4, 'u')]
Output: ['task_id_1', True, True, False, ['task_id_1']]

Explanation: The assignment is active on [1, 4), so completion at time 4 fails and the task is already overdue at time 4.

Hints

1. Store completion time per assignment. An assignment is active at time t only if it has started, not finished, and t is strictly earlier than its completion time.
2. Overdue is a property of each assignment record, not just of a task ID, so do not merge repeated assignments.