Maximum earnings algorithm

Question

How can I calculate the maximum money earned by m tickets in n ticket windows so that the ticket price is equal to the number of tickets in this window?

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

For example, if we have 3 windows with tickets, there are 3, 3, 4 tickets, and we want to sell 5 tickets. Then:

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

The maximum salary is 4 + 3 + 3 + 3 + 2 = 15

I saw this question online, and my solution is to click all ticket numbers on maxHeap first and start the for loop several times. Each time we set the upper value of maxHeap and add it to the total amount of money earned, and if the value is greater than 1, we click (value - 1) on maxHeap.

But is it somehow too much time to resolve any decisions?

Answer 1

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

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

Let x be the maximum number of tickets remaining in the window, so money in one window i contribute to the total income

 (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, the time complexity is O (n log m), where n is the window number and m is the maximum number of tickets in one window.

Answer 2

If you use the maximum heap, this can be done in O (m * logn). Here is the C ++ code -

 int main() { int *inputArray; int n; int m; cin >> n; cin >> m; inputArray = new int[n]; for (int i = 0; i < n; i++) { cin >> inputArray[i]; } cout << maximize(inputArray, n, m) << "\n"; return 0; } int maximize(int *inputArray, int n, int m){ vector<int> v(inputArray, inputArray + n); int sum = 0; // make max heap make_heap(v.begin(), v.end()); for (m = 4; m != 0; m--) { // get max value int max = v.front(); // move max value to end and heapify pop_heap(v.begin(), v.end()); // pop it out v.pop_back(); sum = sum + max; if (max - 1) { // insert m-1 into vector v.push_back(max - 1); // heapify the new vector push_heap(v.begin(), v.end()); } } return sum; } 

Answer 3

  package package1; import java.util.Arrays; import java.util.Scanner; public class RailwayStation{ int numOfTickets, ticketsToSell; int[] ticketsPerBooth; public RailwayStation(int numOfTickets, int ticketsToSell, int[] ticketsPerBooth) { this.numOfTickets = numOfTickets; this.ticketsToSell = ticketsToSell; this.ticketsPerBooth = ticketsPerBooth; } public int findMaxRevenue() { int[] perBooth = this.ticketsPerBooth; Arrays.sort(perBooth); int i = perBooth.length-1; int revenue = 0; while(i>=0 && ticketsToSell!=0){ int diff = 0; if(i==0){ diff = 1; }else{ diff = perBooth[i] - perBooth[i-1]; } while(diff!=0 && ticketsToSell!=0){ revenue = revenue + perBooth[i]; perBooth[i]--; diff--; ticketsToSell--; } if(ticketsToSell!=0 && i==0){ i = perBooth.length-1; }else{ i--; } } return revenue; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int numOfBooths = sc.nextInt(); int ticketsToSell = sc.nextInt(); int perBooth[] = new int[numOfBooths]; for(int i = 0; i < numOfBooths; i++) { perBooth[i] = sc.nextInt(); } RailwayStation rt = new RailwayStation(numOfBooths, ticketsToSell, perBooth); System.out.println("Max Revenue = " + rt.findMaxRevenue()); } } 

Answer 4

"" modified factorial, which is summed up to the limit of the round index ""

def modified_fact (limit, number): sum_fact = 0 for i in the range (number - limit + 1, number + 1): sum_fact + = i return sum_fact

'' "I calculated how many rounds I will need to do to reduce. And in the last iteration, to what index will I need to iterate.

'' '

def maximum_earning_algorithm (n, windows): ""

 :param windows: :param n: :rtype: int """ money = 0 final_round_limit_index = n % len(windows) rounds = n / (len(windows)) print final_round_limit_index, rounds for i in range(len(windows)): if i < final_round_limit_index: money += modified_fact(rounds + 1, windows[i]) else: money += modified_fact(rounds, windows[i]) return money 

if name == ' main : window = [5, 4, 3] print max_earning_algorithm (3, window)

Answer 5

Approach 1)
As @nm pointed out a small optimization of the MaxHeap solution:

You do not need to delete tickets one by one. If you have a top window, you need to know how many tickets he has and how many tickets the next one has. Then you can remove the difference and calculate the total price for one operation. With minor changes, you can do the same if you have multiple windows with the same maximum number of tickets.

---

Approach 2) using a sorted array:

Load the windows into the array. Sort an array. Go back through the array and how you do it: save this number (current), add it to the aggregator, go to the next value. If this is the same (current), then add it to the aggregator, subtract 1 from it, continue driving. If everything is different, go back to the end of the array and start again. Do it N times (inner loop, not outer loop).

---

Approach 3) using the count array (linear time complexity):

• Create an array with index as not. tickets and valuables are gone. from kiosks that have a lot of tickets. So, {0-> 0, 1-> 1, 2-> 0, 3-> 2} means that 1 stall has 1 ticket, and 2 kiosks have 3 tickets)

• Start with the highest array index (count -1) and add this index to your aggregator (A), so A = 3, and then decrease this index (3) by 1 to 1 and increase the index below (= 2) by 1 to one.
  The array is {0,1,1,1} and A = 3. Repetition. A = 6, the array is {0,1,2,0}. The last index is zero, so move the pointer to index 2.
  Repeat so that A = 8, array = {0,2,1,0}. Reiteration. A = 10, the array is {0,5,0,0}.
  Stop when you have done this t times (for the number of tickets sold).

Here's the implementation of this approach:

 int[] stalls = new int[] { 3,1,3 }; // 2 stalls have 3 tickets each and 1 stall have 1 ticket int t = 4; Arrays.sort(stalls); int tickets = stalls[stalls.length - 1]; int[] dp = new int[tickets + 1]; for (int i = 0; i < stalls.length; i++) { dp[stalls[i]]++; } int total = 0; int i = dp.length - 1; while (t > 0) { if (dp[i] > 0) { total += i; t--; dp[i]--; dp[i - 1]++; } else { i--; } } System.out.println(total);