Last Updated: 25 Apr, 2021
Apartments
Moderate
Asked in company
Ninja is a contractor and currently building a society. His work is about to finish. There are 'M' free apartments in the society. The size of each of the apartments is given in an array 'apartmentSize'. He put an online ad for the sale of flats in the society. He received 'N' applications with the desired size of the apartments needed for each applicant. The desired size of the apartments for each applicant is given in an array ‘desiredSize’. Ninja is also provided with an integer 'K'. For any applicant with the desired size of the apartment = D, he will buy the apartment if the size of the apartment lies in between D - K and D + K (both inclusive). He wants to distribute the apartments in such a manner that he can sell as many apartments as possible.
Ninja is very busy finishing the construction works. Can you help Ninja to calculate the maximum number of apartments he can sell?
Input Format :
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.
The first line of each test case contains three space-separated integers ‘N’, ‘M’, and ‘K’, which denotes the number of applicants, the number of free apartments, and the maximum allowed difference.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array ‘desiredSize’.
The third line of each test case contains 'M' space-separated integers denoting the elements of the array ‘apartmentSize’.
Output Format :
For each test case, print the number of apartments Ninja can sell.
Print the output of each test case in a separate line.
Note :
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 50
1 <= N, M <= 10^3
0 <= K <= 10^9
1 <= desiredSize[i], apartmentSize[j] <= 10^9
Where 'desiredSize[i]' denotes the desired size of the apartment of i’th applicant, 'apartmentSize[i]' denotes the size of the apartment at index ‘i’.
Time Limit: 1 sec
Approaches
The idea is to sort both the arrays and then start searching from the beginning. If the size of the apartment lies in the range of the desired size, then we will give the apartment to the person. Otherwise, if the size of the desired apartment is too big, then we will move to the next apartment to search for, and if the size of the apartment is too small, then we will skip the apartment and move to the next applicant. The intuition behind the approach is that we have the sizes of all the desired apartments and the given size of the apartments in ascending order which means instead of searching over all the apartments for a single person, we are iterating over both the arrays. If it suits the person, sell it to the current person. Otherwise, change the person or apartment accordingly. In this approach, we don’t need to check all the apartments for a single person.
Algorithm :
- Initialize an integer answer to 0 to store the answer.
- We will sort both the given arrays desiredSize and apartmentSize.
- We will initialize two integers, i and j, to 0, denoting the pointers for desiredSize and apartmentSize, respectively.
- We will execute a while loop with the condition i is less than the number of applicants, i.e., N and j is less than the number of apartments available, i.e., M.
- If we find a suitable apartment, i.e., the absolute difference between the size of the current apartment and the size of the desired apartment is less than or equal to k, then sell the apartment to the person. We will increment the answer, move to the next person and next apartment, i.e., increment i and j, respectively.
- Otherwise,
- If the desired apartment size of the applicant is too big, i.e., the absolute difference between the size of the current apartment and the size of the desired apartment is greater than k, we will move to the next apartment. Increment j to find a suitable apartment.
- Otherwise, if the desired apartment size of the applicant is too small, i.e., the absolute difference between the size of the current apartment and the size of the desired apartment is less than k, we will move to the next person. Increment i, to find a suitable applicant.
- We will return the variable answer as the final answer.