Concert Tickets

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
5 upvotes
Asked in company
Microsoft

Problem statement

There is a song concert going to happen in the city. There are ‘N’ tickets available for the concert each with a certain price. The prices of ‘N’ tickets are given in an ‘N’ sized ‘price’ array. There are ‘M’ customers which come one by one in order to buy a ticket. Each customer offers a maximum price he or she can pay to buy a ticket. The maximum price offered by ‘M’ customers are given in an ‘M’ sized ‘pay’ array. The customer will get the ticket at the nearest possible price which will not exceed their offered maximum price. Your task is to return the price at which each customer will buy a ticket. If a particular is not able to buy the ticket, then consider -1 as the ticket cost in that case.

Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test case contains two space-separated integers ‘N’ and ‘M’, denoting the number of tickets and the number of customers respectively.

The second line of each test case contains ‘N’ space-separated integers denoting the price of tickets.

The third line of each test case contains ‘M’ space-separated integers denoting the maximum price each customer can pay to buy a ticket.
Output format: 
For each test case, print 'N' space-separated integers denoting the price at which each customer will buy a ticket. 

Print the output for each test case in a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N , M <= 10^4
1 <= price[i] , pay[i] <= 10^9 

Where ‘T’ represents the number of test cases, ‘N’ represents the total number of tickets, ‘M’ represents the total number of customers, 'price[i]' represents the cost of the 'i'th' ticket, and 'pay[i]' represents the maximum price 'i'th' customer can pay to buy a ticket.


Time Limit: 1 sec
Sample Input 1:
2
1 2
1
10 10
5 3
5 3 7 8 5
4 8 3
Sample Output 1:
 1 -1
 3 8 -1
Explanation 1:
For the first test case,
There is only one ticket with a price of 1 unit, and the number of customers to buy tickets are 2. The first person comes and offers a maximum price of 10 units so he gets the ticket by paying 1 unit as price. Now tickets left are 0. So when the second person comes and offers a price of 10 units, he will not get the ticket as there are no tickets left. So the output is {1, -1}.     

For the second test case,
There are 5 tickets with prices as {5, 3, 7, 8, 5}, and the number of customers to buy tickets are 3. The first person comes and offers a maximum price of 4 units so he gets the ticket by paying 3 units as price. The tickets left are {5, 7, 8, 5}. The second person comes and offers a maximum price of 8 units so he gets the ticket by paying 8 units as price. The tickets left are {5, 7, 5}. The third person comes and offers a maximum price of 3 units so he will not get the ticket as there is no ticket left with a price less than or equal to 3. So the output is {3, 8 , -1}.
Sample Input 2:
2
3 2
1 2 3
2 2
4 4
10 10 10 10
10 1 1 1
Sample Output 2:
 2 1
 10 -1 -1 -1
Hint

Find the greatest price which is smaller than or equal to the maximum price offered by the customer.

Approaches (2)
Brute Force

 

  • It is a brute force approach where we will find the greatest ticket price for each customer which is smaller than or equal to the maximum price offered by the customer which is not already sold.
  • To check which ticket has been sold or not we will maintain a visited array.
  • To check which ticket has been sold we will make a temporary variable maxPrice initialized to -1. If its value changes then that means the ticket has been bought at a price equal to the value stored in a variable maxPrice. Otherwise, the customer did not get the ticket.
  • So for each customer, we will iterate over all the tickets and find that ticket that is not sold and its price is greatest among all the tickets having a price lesser than the maximum offered price by the customer.

 

 

Algorithm:

 

  • Create an array visited of size equal to the N and initialize the whole array with false as initially none of the tickets are sold.
  • Also, create an array ans of size M to store the answer.
  • Now iterate through every customer from i = 0 to i = M and perform the following steps:
    • Create a variable maxPrice equal to -1 which will store the answer for the current customer.
    • Create another variable index = 0 to store the value of the index of the ticket which is sold.
    • Now iterate through the price array from j = 0 to j = N and perform the following steps:
      • If the price[j] is smaller or equal to the current customer maximum offered price i.e pay[i] and visited[j] is equal to false:
        • If maxPrice is less than the price[j] then update maxPrice with the price[j] and update the index with j.
    • Now if the value of maxPrice is equal to -1, then insert -1 in the array ans as that there is no ticket among the available ones which the customer could buy.
    • Otherwise, insert maxPrice in the array ans and also update visited at location index as true.
  • Return the array ans.
Time Complexity

O(M*N), where ‘N’ is the total number of tickets and ‘M’ is the total number of customers.

 

Since for every customer we are traversing through the price array which takes a total of O(N) time per customer. So overall time complexity will be O(M*N).

Space Complexity

O(N) where ‘N’ is the total number of tickets.

 

Since the visited array is created which takes O(N) space. So overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Concert Tickets
Full screen
Console