Amazon AS OA：给剩余预算，怎样完成最多任务

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练输入时间非负、任务独立、可自由分配预算；所有任务完成价值相同。
• 已完成任务剩余成本记0并计入总完成数；若只数新增完成，单独扣除初始已完成数量。

解题路线

1. 构建remaining=max(0,required-spent)。题目给的spent是已经沉没的投入，不应该按required或spent大小排序。
2. 升序消耗预算，遇到第一个超过剩余预算就停止。选k个任务的最小总额是k个最小remaining之和，因此若这个前缀超过预算，任何k个任务都不可能更便宜。
3. 已经完成或spent超过required的任务不额外耗时，示例保留它们；若超额spent在正式输入中非法，应校验而非偷偷改变口径。
4. 该贪心依赖等价值与无依赖。任务有不同奖励改为背包，有前置关系要考虑依赖闭包，不能照搬“缺口最小”。

手动走一遍

训练例required=[8,4,10]、spent=[7,0,7]、budget=4，remaining=[1,4,3]，选缺口1与3完成2项。若budget=0，已完成项仍计数。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def max_completed(required, spent, budget):
    """Count already complete tasks too; no partial-completion reward."""
    if len(required) != len(spent) or budget < 0:
        raise ValueError("invalid lengths or budget")
    if any(v < 0 for v in (*required, *spent)):
        raise ValueError("negative task time")
    count = 0
    for cost in sorted(max(0, a-b) for a, b in zip(required, spent)):
        if cost > budget:
            break
        budget -= cost
        count += 1
    return count

复杂度

排序O(n log n)，remaining存储O(n)。仅求数量且成本有界可用频次桶；题目未明确范围，不预设桶大小。

易错点与追问

容易失分的边界

• 按总时长排序。
• 把spent再计入未来预算。
• 不同价值仍宣称该贪心最优。

继续深挖

• 只统计新增完成数量怎样改？
• 任务有依赖怎么建模？
• 预算很多次查询能否用排序前缀和二分？