# Concert Tickets

Posted: 29 Apr, 2021

Difficulty: Moderate

#### 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
```

Approach 1

- 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

- If the
- 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.

- Create a variable
- Return the array
**ans**.

Approach 2

- 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**.