Day 9 : Football Game

Easy
0/40
Average time to solve is 20m
14 upvotes
Asked in companies
UberAmazonBYJUS

Problem statement

Monk's favorite game is Football and his favorite club is "Manchester United". Manchester United has qualified for the Champions League Final which is to be held at the Wembley Stadium in London. So, he decided to go there and watch his favorite team play. After reaching the stadium, he saw that many people have lined up for the match tickets. He knows that there are 'M' rows in the stadium with different seating capacities. They may or may not be equal. The price of the ticket depends on the row. If the row has 'K' vacant seats, then the price of the ticket will be 'K' pounds. Now, every football fan standing in the line will get a ticket one by one.

You are given 'N' number of fans waiting for the tickets and seating capacities of different rows. The club wants to gain maximum pounds with the help of ticket sales.

Your task is to print the maximum possible pounds that the club will gain with the help of ticket sales.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains two integers 'M', and 'N', where 'M' denotes the number of rows and 'N' denotes the number of fans waiting in the line to get a ticket.

The second line contains 'M' single space-separated integers where 'VACANT_SEATS[i]' denotes the number of seats initially empty in the ith row.
Output Format: 
For each output, print a single integer denoting the maximum pounds the club will earn.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= 'M' <= 5 * 10^5 
1 <= 'N' <= 10^9 
1 <= 'VACANT_SEATS[i]' <=10^9 

Time Limit: 1 sec
Sample Input 1:
4 5 
2 3 1 4
Sample Output 1:
14
Explanation For Sample Input 1:
We have 5 people waiting in line and the possible prices are 2, 3, 1 and 4 (in pounds). 
The 1st person is given a ticket in the 4th row worth 4 pounds. Updated possible prices are 2, 3, 1, 3 (in pounds).
The 2nd person is given a ticket in the 4th row worth 3 pounds. Updated possible prices are 2, 3, 1, 2 (in pounds).
The 3rd person is given a ticket in the 2nd row worth 3 pounds. Updated possible prices are 2, 2, 1, 2 (in pounds).
The 4th person is given a ticket in the 2nd row worth 2 pounds. Updated possible prices are 2, 1, 1, 2 (in pounds).
The 5th person is given a ticket in the 1st row worth 2 pounds. Updated possible prices are 1, 1, 1, 2 (in pounds).

Hence, the total money collected is ( 4 + 3 + 3 + 2 + 2 ) = 14 pounds.
Sample input 2:
6 9
1 5 7 3 9 12
Sample output 2:
81
Hint

One fine approach to the problem can be to sort the array and work on the row with maximum vacant seats and earn the maximum pounds possible until the row with maximum vacant seats changes.

Approaches (1)
Sorting

Lets first discuss the approach in steps with an example,

 

  1. The idea is to initially sort the array.
  2. Now, let the sorted array be {1, 2, 4, 6, 8} and the number of fans is 8. The team can sell a ticket of 8 pounds and again a ticket of 7 pounds as the maximum number of vacant seats remain in the last row only.
  3. The number of vacant seats thus becomes {1, 2, 4, 6, 6} and the number of fans becomes 6. Now, we can sell 2 tickets of 6 pounds and 2 of 5 pounds i.e 2 * (6 + 5) pounds can be earned.
  4. The number of vacant seats thus becomes {1, 2, 4, 4, 4} and the number of fans becomes 2. Now, we can sell 3 tickets of 4 pounds and 3 of 3 pounds i.e 3 * (4 + 3) pounds can be earned but the number of fans in the queue is 2. Thus, we can sell 2 tickets worth 4 pounds.

 

Algorithm:

 

  1. Sort the given array.
  2. Maintain a counter variable C and initialize it by 1.
  3. Maintain a variable ANS to store the answer and declare it with 0.
  4. Iterate over the array from the end.
    • If‘N is less than or equal to zero, break.
    • Initialize DIF = VACANT_SEATS[i] - VACANT_SEATS[i - 1].
    • If N >= DIF * C, we will add the sum of sequence (VACANT_SEATS[i - 1] + 1, VACANT_SEATS[i - 1] + 2,...,VACANT_SEATS[i - 1] + DIF - 1), C number of times.
    • Otherwise, initialize X = N / C, MAX= VACANT_SEATS[i - 1] + DIF
      • If X > 0, we will add the sum of sequence (MAX - X + 1, MAX - X + 2,..., MAX), C number of times. Decrease N by X * C and MAX by X.
      • Add (MAX * N) to ANS and now there is no person left, N = 0.
    • Decrease N by DIF * C, Increase C by 1.
  5. If N is still greater than zero,
    • Decrease C by 1.
    • Initialize X = N / C, MAX = VACANT_SEATS[0]
      • If X > 0, we will add the sum of sequence (MAX - X + 1, MAX - X + 2,..., MAX), C number of times. Decrease N by X * C and MAX by X.
      • Add (MAX * N) to ANS and now there is no person left, N = 0.
  6. Print ANS.
Time Complexity

O(M * logM)) where ‘M’ is the number of seating rows.

 

We are iterative on an array containing vacant cases also In the worst case, we are sorting the array that contains the number of vacant seats in the ‘M’ number of rows. Hence the overall time complexity will be O(M * logM). 

Space Complexity

O(1)

 

We are using constant space here. 

Code Solution
(100% EXP penalty)
Day 9 : Football Game
Full screen
Console