Baker
first, consider how to solve for baker 1. let’s say the currently active orders are at times in increasing order. first, note that if we want to fulfill all orders, it is both necessary and sufficient that for all . from this, it follows that the maximum number of orders we can fulfill is .
in general, baker can fulfill
orders. we can see this problem as finding the minimum of lines at . for general queries, note that the active set of indices for a given query is always a contiguous range. therefore the problem reduces to the following:
we are given a collection of lines where line has slope . for queries , find the minimum of among lines .
this can be solved with divide and conquer in time by noting that the lines are already sorted by slope, and therefore convex hull can be run in linear time.