Maximum profit from unit-time tasks with deadlines: Frontier Interview's solution

Question: Maximum profit from unit-time tasks with deadlines

Companies: Airbnb

Difficulty: Medium

Problem statement

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.

Approach

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.

Push the current task.
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.

Code

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")

Complexity

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.

Test cases

[["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.

Follow-ups

Return only the maximum profit. Drop the final sort; return the sum.
Same complexity.
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.
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.
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.
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.

Interviewer expectations

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.