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?
Advertisement
Answer
I would guess that the best to have sorted arrays by the remaining capacities of the non-empty warehouses. A binary search would find the possible warehouses in O(logN) as all leaves greater than A[i] would be candidates. However I don’t see any possibility to fulfill the second condition (the warehouse with the smallest has to be chosen) below O(N) in worst case.