Apartments

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

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

In the first test case, there are 5 applicants with the desired size of apartments as 2, 40, 2, 50, and 2 respectively, and the number of apartments available is 3 with the size of the apartments as 35, 50, and 30 respectively. He can sell the first apartment with size 35 to the first person with the desired size of the apartment 40 as he/she can take an apartment whose size is in the range of 40 - K and 40 + K, i.e., 30 and 50 and the second apartment with size 50 to the second person with the desired size of the apartment 50. So, the answer is 2 in this case. In the second test case, there are 3 applicants with the desired size of apartments as 5, 7, and 8, respectively. The number of apartments available is 3, with the size of the apartments as 15, 20, and 15 respectively. He will not be able to sell any apartment as the desired apartment size is not in the given range of the sizes of the apartments. So, the answer is 0 in this case.

Sorting Based Solution

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.

Time Complexity

O(N*log(N) + M*log(M)), where ‘N’ is the number of applicants and ‘M’ is the number of apartments.

As we are sorting both the arrays, which takes O(N*log(N) + M*log(M)) time and using two pointers i and j to iterate through the two arrays, which takes O(N + M) time in the worst case. Hence, the overall time complexity is O(N*log(N) + M*log(M)).

Space Complexity

O(1).

As we are using constant extra space. Hence, the overall space complexity is O(1).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation For Sample Input 1 :

Sample Input 2 :

Sample Output 2 :