A single worker has a pile of chores, each given as three strings [name, deadline, reward], e.g. ["wash-car", "2", "40"]. Every chore takes exactly one second. The worker starts at time 0 and does at most one chore per second: the chore done first occupies [0, 1) and finishes at time 1, the next finishes at time 2, and so on. A chore only pays its reward if it finishes at or before its deadline; chores that can't make it are simply skipped.
Write plan_tasks(tasks: list[list[str]]) -> tuple[int, list[str]] that returns:
- the largest total reward the worker can earn, and
- a schedule achieving it: the names of the chosen chores in the order they are done. Each chosen chore at position
i(0-based) finishes at timei + 1, which must not exceed its deadline.
If several schedules reach the maximum, return any of them (the tests check that yours is valid and earns the maximum). Chores with reward 0 may be included or left out.
Details: names are distinct non-empty strings; deadline and reward are decimal integers with 0 <= deadline <= 10**9 and 0 <= reward <= 10**9. A deadline of 0 means the chore can never be done. An empty list gives (0, []).
plan_tasks([["a", "2", "10"], ["b", "1", "19"], ["c", "2", "27"], ["d", "1", "25"], ["e", "3", "15"]])
# (67, ["d", "c", "e"]) d finishes at 1, c at 2, e at 3; ["c", "d", "e"] would miss d's deadline
plan_tasks([["x", "0", "99"]])
# (0, [])
Up to 10**5 chores. Deadlines are huge, so an array with one slot per second won't fit.
Show hint
Go through the chores by increasing deadline, keeping the chosen ones in a min-heap by reward. Add each chore; if the heap now holds more chores than its deadline allows, drop the cheapest one. At the end, sort the survivors by deadline: doing them in that order meets every deadline.