Last Updated: 29 Apr, 2021
Concert Tickets
Moderate
Asked in company
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.
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
Approaches
- 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.
- 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:
- 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.
- Since we need to find the ticket with a price less than or equal to the maximum price offered by each customer. So we will use the upper bound to fulfill this purpose.
- Now to use the upper bound the price array should be sorted and it can have duplicate values so we will insert all the values of the price array in a multiset which will fulfill our requirements.
- Since the upper bound will give us the iterator pointing to the first element greater than the value passed as a parameter.
- So for each value of maximum price offered by the customer, we will find its upper bound in the multiset and get an iterator to it. If the iterator is pointing at the beginning then that means there are no tickets that are less than or equal to the maximum price offered. Otherwise, decrement the iterator to make the iterator point to a value less than or equal to the maximum price offered by the customer and print the value pointed by that iterator and erase that element from the multiset as this ticket has been sold.
Algorithm:
- Create a multiset maxPrice and insert all the given values of the price array into the multiset.
- Create an array ans to store the answer for each customer.
- Now iterate through each customer and for the maximum price offered by each customer find its upper bound in the multiset maxPrice and get an iterator through it.
- So if the iterator is pointing to the beginning of the multiset then simply insert -1 for that customer i.e he/she will not get a ticket.
- Otherwise, decrement the iterator and insert the value in the array pointed by that iterator and then erase that value from the multiset.
- Return the array ans.