Maximum profit from unit-time tasks with deadlines

Every task takes one second, so a schedule is just a set of tasks plus an
order. The order part is easy: if a set of tasks can be done at all, it can
be done in earliest-deadline-first order. (Swap any two adjacent tasks
that are out of deadline order; the earlier-deadline task only moves earlier,
and the later-deadline task moves into a slot that ends no later than the
earlier task's old slot, which met a smaller deadline.) So a set S is
feasible exactly when, for every d, at most d tasks in S have a
deadline <= d.

The real question is which set to pick.

Brute force. Try all 2^n subsets, check feasibility with the rule above,
and keep the best. O(2^n * n log n). Fine for describing the shape of the
problem, useless past ~20 tasks.

Greedy by profit, latest free slot (classic). Sort by profit descending.
Place each task in the latest free slot <= deadline; skip it if there is none.
With a linear scan this is O(n * D); with a union-find "next free slot"
pointer it is near O(n log n). It works, but the slot array is sized by the
largest deadline, which can be huge (deadlines are given as strings and can be
10^9). Cap the slot count at n to fix that.

Optimal and simple: sort by deadline + min-heap. Walk tasks in increasing
deadline order and keep a min-heap (by profit) of the tasks we currently plan
to run.

1. Push the current task.
2. If the heap now holds more tasks than the current deadline allows, pop the
   cheapest one.

Invariant: after processing all tasks with deadline <= d, the heap is the
most profitable feasible set among those tasks. Adding a task with deadline
d keeps the set feasible unless the count exceeds d, and then removing the
single cheapest task restores feasibility with the least possible loss (an
exchange argument: any optimal set must drop at least one task here, and
dropping the cheapest is never worse). Tasks with deadline 0 or less, or
profit <= 0, can never help and are skipped up front.

At the end, the heap is the chosen set. Sort it by deadline (ties by name for
a deterministic answer) to get a valid execution order.

Input parsing: deadline and profit arrive as strings, so convert with
int() and reject bad rows early with a clear error.

import heapq
from typing import List, Tuple


def max_task_rewards(tasks: List[List[str]]) -> Tuple[int, List[str]]:
    """
    tasks[i] = [name, deadline, profit] (all strings).
    Each task takes exactly 1 second; one task per second, starting at t=0.
    A task in slot [t, t+1) is on time if t + 1 <= deadline.
    Returns (max total profit, task names in execution order).
    """
    parsed: List[Tuple[int, int, str]] = []
    for row in tasks:
        if len(row) != 3:
            raise ValueError(f"bad task row: {row!r}")
        name, deadline_s, profit_s = row
        deadline, profit = int(deadline_s), int(profit_s)
        if deadline <= 0 or profit <= 0:
            continue  # can never be scheduled on time, or never helps
        parsed.append((deadline, profit, name))

    parsed.sort()  # by deadline, then profit, then name

    chosen: List[Tuple[int, str, int]] = []  # min-heap of (profit, name, deadline)
    for deadline, profit, name in parsed:
        heapq.heappush(chosen, (profit, name, deadline))
        if len(chosen) > deadline:
            heapq.heappop(chosen)  # drop the cheapest task to stay feasible

    total = sum(profit for profit, _, _ in chosen)
    order = [name for _, name, _ in sorted(chosen, key=lambda t: (t[2], t[1]))]
    return total, order


def is_valid_schedule(tasks: List[List[str]], order: List[str]) -> bool:
    """Checks that `order` runs each named task once and on time."""
    deadlines = {name: int(d) for name, d, _ in tasks}
    if len(set(order)) != len(order):
        return False
    return all(t + 1 <= deadlines[name] for t, name in enumerate(order))


if __name__ == "__main__":
    t1 = [["a", "2", "100"], ["b", "1", "19"], ["c", "2", "27"],
          ["d", "1", "25"], ["e", "3", "15"]]
    assert max_task_rewards(t1) == (142, ["a", "c", "e"])
    assert is_valid_schedule(t1, max_task_rewards(t1)[1])

    t2 = [["x", "1", "5"], ["y", "1", "9"], ["z", "1", "7"]]
    assert max_task_rewards(t2) == (9, ["y"])

    assert max_task_rewards([]) == (0, [])
    assert max_task_rewards([["late", "0", "50"], ["free", "3", "0"]]) == (0, [])

    t3 = [["p", "1000000000", "4"], ["q", "1000000000", "6"]]
    assert max_task_rewards(t3) == (10, ["p", "q"])

    t4 = [["a", "3", "10"], ["b", "3", "20"], ["c", "3", "30"], ["d", "3", "40"]]
    assert max_task_rewards(t4) == (90, ["b", "c", "d"])
    print("ok")

• Parsing: O(n).
• Sort by deadline: O(n log n).
• Heap pass: each task is pushed once and popped at most once, O(n log n).
• Final ordering: O(k log k) for k <= n chosen tasks.
• Space: O(n). Nothing depends on the size of the deadlines, so a deadline
  of 10^9 costs the same as a deadline of 3.

• [["a","2","100"],["b","1","19"],["c","2","27"],["d","1","25"],["e","3","15"]]
  → (142, ["a","c","e"]). Only one task can use the first second and two
  tasks share deadline 2, so a and c win those slots and e takes second 3.
• Three tasks all due at 1 with profits 5, 9, 7 → (9, ["y"]).
• Empty input → (0, []).
• Deadline "0" or profit "0" → skipped → (0, []).
• Huge deadlines "1000000000" with two tasks → both run, (10, ["p","q"]).
• Four tasks due at 3 with profits 10, 20, 30, 40 → drop the 10, (90, ["b","c","d"]).
• Row with two fields, or "abc" as a deadline → ValueError.

1. Return only the maximum profit. Drop the final sort; return the sum.
   Same complexity.
2. Tasks have different durations. Now it is a weighted scheduling problem
   with deadlines and durations, which is NP-hard in general (it contains
   knapsack). Offer a DP over time dp[t] = best profit finishing by t when
   the horizon is small, or a pseudo-polynomial DP over tasks sorted by
   deadline. If tasks also have fixed start/end times, it becomes LeetCode
   1235: sort by end time and binary-search the last compatible task.
3. k workers instead of one. A set is feasible when at most k * d
   tasks have deadline <= d. Change the heap check to
   len(chosen) > k * deadline; to output a schedule, deal the
   earliest-deadline-first order round-robin across workers.
4. Tasks stream in, query the best profit at any time. Inserting a task
   with an early deadline can evict tasks at later deadlines, so the single
   left-to-right pass no longer works. Use the latest-free-slot greedy with a
   balanced tree or a segment tree over compressed deadlines that tracks slack
   (d - count(deadline <= d)); when there is no slack, replace the cheapest
   chosen task in the affected prefix if the new one pays more.
5. Ties and determinism. Interviewers often ask which schedule to return
   when several reach the same profit. State a rule (e.g. prefer fewer tasks,
   then lexicographically smallest names) and encode it in the heap key.

Mid-level (L4)

• Notices that unit durations make order easy and selection the real problem.
• Reaches a correct greedy (profit-descending with slots, or deadline + heap)
  and parses the string inputs correctly.
• Walks through an example by hand and handles empty input and deadline 0.

Senior (L5)

• Explains why earliest-deadline-first order is always valid and why dropping
  the cheapest task keeps the heap optimal.
• Avoids an array sized by the largest deadline.
• Returns a real execution order and verifies it, and states complexity per step.

Staff (L6+)

• Separates "which set" from "what order" cleanly and argues optimality with
  an exchange argument or a matroid view.
• Sees where the greedy breaks (varying durations, fixed intervals) and names
  the right tool for each.
• Discusses multiple workers, streaming inserts, and deterministic tie rules
  without restarting the design.