Concert Tickets

Posted: 29 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
    • 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.
Try Problem