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.
This problem is a classic fixed-size sliding window task. Given minute-level arrival probabilities and a window length K, we need to find the contiguous interval of length K with the maximum total probability, then return its lower and upper bounds as the best ETA window. A linear-time solution using sliding window or prefix sums is sufficient, and the key detail is to track the best window boundaries while respecting the minimum valid minute.
