DoorDash OA 面试真题解析：Assigning Multiple Orders to a Dasher（网格动态规划 / 拓扑路径）

Assigning Multiple Orders to a Dasher

DoorDash optimizes Dasher efficiency by assigning multiple orders from nearby restaurants to the same Dasher. This is called order stacking. Given a city map consisting of restaurants that have orders ready to be picked up at a specified time, determine the maximum number of orders that can be stacked/assigned to a single Dasher.

Cell i, j of city represents a restaurant, and city[i][j] represents the time at which an order is ready to be picked up from the restaurant.

An order can be assigned to the same Dasher if:

• The next restaurant is directly adjacent to the previous restaurant where an order was picked up.
• The pickup time for the next order is after the pickup time of the last order that was picked up.

Example 1:

Provided:

city = [[9, 9, 4],
    [6, 6, 8],
    [2, 1, 1]
]

Return:

maximumStackedOrders = 4

这道题本质上是在网格中寻找一条“严格递增且相邻移动”的最长路径。每个餐厅格子对应一个可取餐时间，Dasher 只能从当前餐厅走到上下左右相邻、且时间更晚的餐厅，因此可以把每个格子看成图中的一个节点，用 DFS + 记忆化搜索或动态规划求出从每个位置出发能形成的最长链，最后取最大值。示例中通过在 3×3 网格里不断选择相邻且更大的时间点，最长可串联 4 个订单。