1

Concert Tickets

Difficulty: MEDIUM
Contributed By
Archit Sharma
Avg. time to solve
20 min
Success Rate
80%

Problem Statement
Suggest Edit

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
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
Reset Code
Full screen
copy-code
Console