maximum earning algorithm

Question

How can I calculate the maximum money earned of m tickets of n ticket windows that the price of a ticket is equal to the reamaining number of tickets that window?

There are n ticket windows in the railway station. The with window has a(j) tickets available. The price of a ticket is equal to the number of tickets remaining in that window at that time. What is the maximum amount of money the railway station can earn from selling the first m tickets?

For example if we got 3 ticket windows, have tickets of 3, 3, 4, and we want to sell 5 tickets. Then:

n = 3, m = 5
A[3] = {3, 3, 4}

The maximum money earned is 4 + 3 + 3 + 3 + 2 = 15

I saw this question online and my solution is to first push all tickets numbers to a maxHeap and run a for loop for m times. Every time we pop the top value of the maxHeap and add it to the total money earned and if the value is bigger than 1 we push (value - 1) to the maxHeap.

But this is somehow too time consuming any better solutions?

Answer 1

To solve this problem, we need to make an observation:

• To get the maximum result, we need to get the top most m tickets.

Let x be the maximum number of tickets left in a window, so the money one window i contributes to the total earning is

(a(i) + a(i) - 1 + ... + x + 1) = a(i)*(a(i) + 1)/2 - x*(x + 1)/2

To find x, we can use binary search

int start = 0;
int end = maximum number of ticket in one window;
while(start <= end)
   int mid = (start + end)/2;
   for(each window)
      number of sell ticket += a(i) - mid;//if mid is larger than a(i), just add a zero
   if(number of sell ticket >= m)
      increase start;
   else
      decrease end;

So, time complexity is O(n log m) with n is number of window and m is maximum number of ticket in one window.