Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Generate Maximum revenue by selling K tickets from N windows

Objec­tive: Given ‘N’ win­dows where each win­dow con­tains cer­tain num­ber of tick­ets at each win­dow. Price of a ticket is equal to num­ber of tick­ets remain­ing at that win­dow. Write an algo­rithm to sell ‘k’ tick­ets from these win­dows in such a man­ner so that it gen­er­ates the max­i­mum revenue.

This prob­lem was asked in the Bloomberg for soft­ware devel­oper position.

Exam­ple:

Say we have 6 windows and they have 5, 1, 7, 10, 11, 9 tickets respectively.
Win­dow Number 1 2 3 4 5 6
Tick­ets 5 1 7 10 11 9

 

Sell the first ticket from win­dow 5, since it has 11 tick­ets so cost will be $11.

Revenue after selling first ticket, MaxRevenue: 11.
Win­dow Number 1 2 3 4 5 6
Tick­ets 5 1 7 10 10 9

 

Sell the sec­ond ticket from win­dow 4 or win­dow 5, since they have 10 tick­ets each so cost will be $10, assume we sell it from win­dow 5.

Revenue after selling second ticket, MaxRevenue: 21.
Win­dow Number 1 2 3 4 5 6
Tick­ets 5 1 7 10 9 9

 

Sell the third ticket from win­dow 4, since it has 10 tick­ets so cost will be $10.

Revenue after selling second ticket, MaxRevenue: 31.
Win­dow Number 1 2 3 4 5 6
Tick­ets 5 1 7 9 9 9

 

Sell the fourth ticket from win­dow 4,5 or 6, since they have 9 tick­ets each so cost will be $10.

Revenue after selling fourth ticket, MaxRevenue: 40.

Approach:

  1. Cre­ate a max-heap of size of num­ber of win­dows. (Click here read about max-heap and pri­or­ity queue.)
  2. Insert the num­ber of tick­ets at each win­dow in the heap.
  3. Extract the ele­ment from the heap k times (num­ber of tick­ets to be sold).
  4. Add these extracted ele­ments to the rev­enue. It will gen­er­ate the max rev­enue since extract­ing for heap will give you the max ele­ment which is the max­i­mum num­ber of tick­ets at a win­dow among all other win­dows, and price of a ticket will be num­ber of tick­ets remain­ing at each window.
  5. Each time we extract an ele­ment from heap and add it to the rev­enue, reduce the ele­ment by 1 and insert it again to the heap since after num­ber of tick­ets will be one less after selling.

Com­plete Code:

Output:

Max revenue generated by selling 5 tickets: 49

You may also like...