Implement A Prioritized Task Scheduler With Parent Dependencies

Problem Statement

In a distributed workflow platform, background jobs often depend on the completion of prerequisite parent tasks. You are asked to implement an in-memory TaskScheduler that manages task dependencies, selects the next executable task according to a strict multi-attribute priority order, supports filtering, and gracefully detects circular dependencies.

A task cannot be executed until all of its parent dependencies have been completed. Once a task's dependencies are satisfied, it becomes ready for execution.

Implement the TaskScheduler class with the following methods:

• add_task(task_id: str, parent_ids: list[str], due_date: int, is_high_priority: bool, created_at: int) -> None: Registers a task with its metadata and list of parent prerequisite task IDs.
• complete_task(task_id: str) -> None: Marks a task as finished. This may unblock dependent child tasks, making them ready.
• get_next_task(high_priority_only: bool = False) -> str | None: Retrieves and claims (removes from ready pool) the next highest-priority task ready for execution. If high_priority_only is True, only tasks with is_high_priority == True may be returned. If no matching ready task exists, returns None.
• has_deadlock() -> bool: Returns True if there are remaining incomplete tasks in the scheduler, but none of them can be executed (e.g., due to a dependency cycle or an uncompleted prerequisite that was never added/completed).

Priority Ordering Rules

When multiple tasks are ready, they must be selected using the following tie-breaking hierarchy:

1. Due Date: Lower due_date value (earliest deadline first).
2. Priority: is_high_priority == True before is_high_priority == False.
3. Creation Time: Lower created_at value (earliest created first).
4. Task ID: Lexicographically smaller task_id (e.g., 'task_a' < 'task_b').

Example

scheduler = TaskScheduler()

# Add tasks
# Task A has no dependencies
scheduler.add_task("A", [], due_date=100, is_high_priority=False, created_at=10)
# Task B depends on A
scheduler.add_task("B", ["A"], due_date=50, is_high_priority=True, created_at=20)
# Task C has no dependencies
scheduler.add_task("C", [], due_date=100, is_high_priority=True, created_at=15)

# Ready tasks initially: A and C (B is waiting on A)
# Comparing A vs C:
# Due dates are equal (100 vs 100).
# Priority: C is high priority (True), A is not (False). C wins.
assert scheduler.get_next_task() == "C"

# Next ready task is A
assert scheduler.get_next_task() == "A"

# No ready tasks right now; B is still waiting on A to complete
assert scheduler.get_next_task() == None
assert scheduler.has_deadlock() == False  # A is in-progress / uncompleted

# Complete A, which unblocks B
scheduler.complete_task("A")
assert scheduler.get_next_task() == "B"

# All tasks claimed and completed
scheduler.complete_task("B")
assert scheduler.has_deadlock() == False

Constraints

• 1 <= task_id.length <= 64 (strings containing alphanumeric characters and underscores).
• 0 <= parent_ids.length <= 100.
• 0 <= due_date, created_at <= 10^9.
• add_task will be called at most 10^4 times with unique task_ids.
• complete_task will only be called with valid task_ids that have been claimed via get_next_task or were previously added.