When a consumer places an order with DoorDash, our ETA system provides them with an estimated delivery time window, for example, 5 minutes ~ 15 minutes, with the lower bound greater than 0 minute to prevent unrealistic ETAs.
The accuracy of ETAs is measured by on-time rate, i.e., the percentage of orders whose actual delivery time falls within the predicted window.
Now we have an ML model that predicts the probability of delivery time at the minute level, which is then converted to a window.
Specifically, the ML model returns an array where the value at index i represents the probability of the delivery arriving at the i-th minute.
Given a fixed window size of K minutes, return the optimal window’s lower bound and upper bound to achieve the highest on-time rate.
这道题本质上是一个固定长度的滑动窗口问题：给定按分钟表示的到达概率数组，以及窗口长度 K，需要找到连续 K 分钟内概率和最大的区间，作为最优 ETA 时间窗。解法通常用前缀和或滑动窗口在 O(n) 时间内求出每个长度为 K 的区间和，并记录最大值对应的左右边界。面试中要注意窗口下界不能小于 1（或题目约束中的最小分钟），以及返回的是概率总和最高的窗口，而不是单个分钟概率最高的位置。
