We have m different products (numbered from 1 to m). the tender is open for m days, during these days n people gives an offer to buy(each offer is for one product), At the end of each day the product (form all products that not yet been sold) with the highest offer will be sold .
we should implement a data structure which provides the following operations:
- Init (m)-> initializes the DS with m elements without offers
- Bid(j,p)-> adds an offer with price p to the product j in complexity O(1) amortized
- Sell-> sells the product with the highest offer. return j (the product which was sold) and p (the price in which the product was sold) in complexity O(log m) amortized .
I tried to solve the question by using fibonacce heaps:
we create a new fib heap and insert m times (the products with key j and info null)
I use the idea of decrease key in fib heaps and switch the info with the new p in
I use the idea of delete min to delete the max
So in order to solve the problem I think that I should use max heaps and not min heaps, this makes me think that I'm in the wrong way.
Someone can help me to get the true solution ?! **
You can get O(log M) for Bid(), and O(1) for Sell() by keeping a hash table of products to maximum bid, and a list of product sorted by maximum bid.
For Bid() you update the table if needed, and updated the list with a binary search if needed; For Sell() you simply pop the top item from the list and get the price from the map.