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:

  1. Create a max-heap of size of number of windows. (Click here read about max-heap and priority queue.)
  2. Insert the number of tickets at each window in the heap.
  3. Extract the element from the heap k times (number of tickets to be sold).
  4. 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 price of a ticket will be number of tickets remaining at each window.
  5. Each time we extract an element from heap and add it to the revenue, reduce the element by 1 and insert it again to the heap since after number of tickets will be one less after selling.

Complete Code:

import java.util.Comparator;
import java.util.PriorityQueue;
public class MaxRevenueTickets {
PriorityQueue<Integer> pq;
// we will create a max heap
public MaxRevenueTickets(int length) {
pq = new PriorityQueue<>(length, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o2 o1;
}
});
}
public int calculate(int[] windowsTickets, int tickets) {
int revenue = 0;
// insert the all the elements of an array into the priority queue
for (int i = 0; i < windowsTickets.length; i++) {
pq.offer(windowsTickets[i]);
}
while (tickets > 0) {
int ticketPrice = pq.poll();
revenue += ticketPrice;
pq.offer(ticketPrice);
tickets;
}
return revenue;
}
public static void main(String[] args) {
int[] windowsTickets = { 5, 1, 7, 10, 11, 9 };
int noOfTickets = 5;
MaxRevenueTickets mx = new MaxRevenueTickets(windowsTickets.length);
System.out.println("Max revenue generated by selling " + noOfTickets
+ " tickets: " + mx.calculate(windowsTickets, noOfTickets));
}
}

Output:

Max revenue generated by selling 5 tickets: 49