|
Be the first user to complete this post
|
Add to List |
185. Generate Maximum revenue by selling K tickets from N windows
Objective: Given 'N' windows where each window contains certain number of tickets at each window. Price of a ticket is equal to number of tickets remaining at that window. Write an algorithm to sell 'k' tickets from these windows in such a manner so that it generates the maximum revenue.
This problem was asked in the Bloomberg for software developer position.
Example:
Say we have 6 windows and they have 5, 1, 7, 10, 11, 9 tickets respectively.
| Window Number | 1 | 2 | 3 | 4 | 5 | 6 |
| Tickets | 5 | 1 | 7 | 10 | 11 | 9 |
Sell the first ticket from window 5, since it has 11 tickets so cost will be $11.
Revenue after selling first ticket, MaxRevenue: 11.
| Window Number | 1 | 2 | 3 | 4 | 5 | 6 |
| Tickets | 5 | 1 | 7 | 10 | 10 | 9 |
Sell the second ticket from window 4 or window 5, since they have 10 tickets each so cost will be $10, assume we sell it from window 5.
Revenue after selling second ticket, MaxRevenue: 21.
| Window Number | 1 | 2 | 3 | 4 | 5 | 6 |
| Tickets | 5 | 1 | 7 | 10 | 9 | 9 |
Sell the third ticket from window 4, since it has 10 tickets so cost will be $10.
Revenue after selling second ticket, MaxRevenue: 31.
| Window Number | 1 | 2 | 3 | 4 | 5 | 6 |
| Tickets | 5 | 1 | 7 | 9 | 9 | 9 |
Sell the fourth ticket from window 4,5 or 6, since they have 9 tickets each so cost will be $10.
Revenue after selling fourth ticket, MaxRevenue: 40.
Approach:
- Create a max-heap of size of number of windows. (Click here read about max-heap and priority queue.)
- Insert the number of tickets at each window in the heap.
- Extract the element from the heap k times (number of tickets to be sold).
- Add these extracted elements to the revenue. It will generate the max revenue since extracting for heap will give you the max element which is the maximum number of tickets at a window among all other windows, and the price of a ticket will be the number of tickets remaining at each window.
- Each time we extract an element from the heap and add it to the revenue, reduce the element by 1 and insert it again into the heap since after a number of tickets will be one less after selling.
Output:
Max revenue generated by selling 5 tickets: 49