DoorDash optimizes Dasher efficiency by stacking orders from nearby restaurants for the same Dasher.
Given a 2D grid city where city[i][j] is the ready time of the order at restaurant (i, j), determine the maximum number of orders that can be assigned to one Dasher.
A subsequent order can be assigned to the same Dasher if and only if:
- The next restaurant is directly adjacent (up, down, left, or right) to the previous restaurant, and
- The next order’s ready time is at or after the pickup time of the last order the Dasher picked up (i.e., the sequence of times is non-decreasing).
Return the maximum count of orders that can be stacked for a single Dasher.
Example 1
city = [
[9, 9, 4],
[6, 6, 8],
[2, 1, 1]
]
Output: 4
(One optimal route picks 4 orders while moving only to adjacent cells and never decreasing the ready time.)
Notes: You may start at any restaurant cell. Movement is limited to 4 directions.
这题的核心就是：在二维网格里，只能上下左右走，时间不能下降 （后一单的 ready time ≥ 前一单），问“ 同一个 Dasher 最多能连续接几单”。
面试官要看你是否能把它抽象成：
- 图上的最长路径（受限于相邻与“时间非递减”约束）；
- 用 DFS + 记忆化（或先按时间排序做“从小到大转移”）避免重复计算；
- 明确说明 相同时间可以接（非递减）；
- 支持 任意起点，答案是全局最大值。
思路要点：
- 以
(i, j)为终点，定义best[i][j]= 从这里出发能取得的最长链； - 对四邻居中 时间 ≥ 当前 的格子递归转移并取最大；
- 用 memo 把每个格子的结果缓存，整体 O(mn) 级别（每条边最多被访问一次）。
这是 DoorDash 常见的 路径 + 单调约束 题，既考察建模能力，也考察你把暴力改成工程可行解的功力。
VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Doordash、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Tiktok 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。
