Maximum profit from unit-time tasks with deadlines

You are given a list of tasks. Each task is a list of three strings: [name, deadline, profit].

• Every task takes exactly 1 second, and only one task can run at a time.
• Time starts at 0. A task that runs during second [t, t+1) is on time only if t + 1 <= deadline.
• You earn a task's profit only if it finishes on time. Tasks you do not schedule earn nothing.

Implement:

def max_task_rewards(tasks: list[list[str]]) -> tuple[int, list[str]]:
    ...

Return the maximum total profit and the names of the chosen tasks in the order they run. Order tasks with the same deadline by name so the answer is deterministic.

Constraints

• 0 <= len(tasks) <= 10^5
• Task names are unique.
• deadline and profit are integer strings; 0 <= deadline <= 10^9, 0 <= profit <= 10^9.

Example 1

tasks = [["build", "2", "40"], ["lint", "1", "10"], ["test", "2", "30"], ["ship", "3", "5"]]
-> (75, ["build", "test", "ship"])

Only two tasks fit before second 2, so build and test beat lint. ship still fits in the third second.

Example 2

tasks = [["a", "1", "3"], ["b", "1", "8"], ["c", "0", "50"]]
-> (8, ["b"])

c can never finish on time, and only one of a and b fits in the first second.