I had the following problem on the exam: A certain power plant needs coal to operate, so it has ordered n deliveries, and information about each delivery (number of tons) is stored in a list A. The delivered coal is stored in warehouses with consecutive numbers 0, 1, .... (Their exact number is not given). Each warehouse has the same capacity in tons given by the number T (where T>=A[i] for i=0,1,...,n-1). There are a few rules for storing coal. Coal cannot be split, that is, each shipment must be allocated to only one warehouse. In addition, we always try to put coal into the warehouse with the smallest possible number. The problem is to find the warehouse number where we store the last (n-1) delivery.
For Example:
A = [1, 6, 2, 10, 8, 3, 1]
T = 10
The answer is 0.
Solving O(n^2) of this problem is pretty obvious, but I have no idea how this task could be solved in O(nlogn), and that's the complexity you could get the most points for. Any ideas?