题目重点：Senior Phone Screen/Staff Coding 多次提按 deadline 安排任务最大收益；单位时长训练版按 profit 降序选最晚空位，讨论近似搜索优化。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版每任务恰占 1 个离散时隙，deadline=d 表示可安排到时隙 d（1-based，含 d），同一时隙最多一个任务；利润非负。
- 任务时长可变或依赖任务时，该贪心不保证最优，应换 DP/其他模型。
- 返回最大利润及所选任务，题目只说明 maximize profits，具体返回格式未给。
解题路线
- 按 profit 降序处理任务，若利润相同按输入序保证确定性；当前任务若 deadline 前存在空位，就放在最晚可用时隙，否则跳过。
- 最晚放置保留更早时隙给截止更早的任务。交换论证：任意最优解可将已选的更高利润任务与较低利润任务交换且不降低利润，再把它右移到最晚空位而不损害其他任务。
- 基线从 min(deadline,n) 向左扫描找空位，最坏 O(n²)；优化用并查集 parent[t] 代表 ≤t 的最大可用时隙，安排到 t 后把 parent[t] 指向 find(t−1)。
- 把 deadline 截到 min(d,n) 即可，因为最多安排 n 个任务；检查 d≤0、零利润、相同 deadline、空输入与大量稀疏 deadline。
手动走一遍
训练任务 A=(deadline2,profit50)、B=(1,40)、C=(2,30)：先 A 放最晚时隙 2，B 放 1，总利润 90。若把 A 放最早时隙 1，B 被挤掉，后面 C 最多放 2，只得 80。
规模与取舍
排序 O(n log n)，逐任务向左扫最坏 O(n²)；并查集找空位为近似 O(n α(n)) 均摊，整体 O(n log n) 时间、O(n) 空间。若 deadline 单位不是离散 slot，先按真实范围离散化。
易错点与追问
容易失分的边界
- 把长任务/多机器场景直接套单位任务贪心。
- 选最早空位，浪费紧 deadline 的位置。
- deadline 0 或负数仍安排。
- 用数组反复向左扫而声称 O(n log n)。
- 把 的‘要更优算法’误读为原贪心策略一定错误，实际可能指查找空位的复杂度。
继续深挖
- 任务时长不同时如何建模？
- 如何用并查集找最后空位？
- 任务有依赖或取消时怎么办？
- 要输出按时间顺序的计划如何恢复？
