DoorDash 时间点最少分批：容量 B 与窗口 W 的贪心证明

题意与假设

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

• 时间点可重复，可无序输入，先排序。训练契约把窗口解释为闭区间 [first,first+W]；题目没有精确说明端点是否包含，现场应澄清。
• 每个时间点必须恰好分配一次，批次内部不要求保留原输入顺序；每批最多 B 个，B>0 且 W≥0。
• 优化目标仅为批次数，不考虑批次开启成本、不同任务权重或最大延迟。

解题路线

1. 按时间排序，把最早尚未分配的时间 t 作为下一批首项，向右连续装入所有满足数量≤B 且 time−t≤W 的时间点。
2. 一旦下一个时间超窗或超容量，就关闭当前批次并从下一个时间重复。返回批次列表可直观验证覆盖；若只需要数量，计数即可。
3. 交换论证：任何最优解的第一批都可调整为包含从最早时间开始的最大可行前缀，而不会使剩余点更难分组。归纳到后续前缀，贪心批数最少。

手动走一遍

时间点 [1,3,5]、B=2、W=2 时，第一批可收 [1,3]，第二批为 [5]，共 2 批。若 W=0，则不同时间点不能同批，但相同时间点仍可在容量内合批。

Python 参考实现

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

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

"""Minimum number of capacity and time-window constrained batches."""


def minimum_batches(timepoints: list[int], capacity: int, window: int) -> list[list[int]]:
    if capacity <= 0 or window < 0:
        raise ValueError("capacity must be positive and window nonnegative")
    times = sorted(timepoints)
    batches: list[list[int]] = []
    i = 0
    while i < len(times):
        start = times[i]
        end = i
        while end < len(times) and end - i < capacity and times[end] - start <= window:
            end += 1
        batches.append(times[i:end])
        i = end
    return batches

复杂度

排序 O(n log n) 时间；单次左到右扫描 O(n)；返回全部批次占 O(n) 空间。若输入已经按时间排序，扫描部分 O(n)。

易错点与追问

容易失分的边界

• 窗口必须相对批次第一项判断，而不是只检查与上一项的时间差；[1,3,5] 在 W=2 时三项相邻差都 2，却不能同批。
• 只看容量会把超窗任务塞入当前批；只看窗口会超过 B。两个条件都要检查。
• 若窗口端点采用半开 [first,first+W)，恰好等于 W 的点要排除；示例采用闭区间并显式标注。

继续深挖

• 题目另提到骑手接单背景的 Meeting Rooms II 类追问，那是求并发峰值，应把开始/结束事件排序后扫描；与本题最少分批的贪心目标不同，不直接套同一公式。
• 若任务带权或可选择不处理，最大前缀贪心可能失效，需要重新定义目标并考虑 DP/最短路。