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

Bloomberg

解法：类似于23. Merge k Sorted Lists 合并k个有序链表 用最大堆

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.

Java:

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));

	}

}