Apartments Solution

14 September 2021

Statement

( The original statement can be found here )
There are n applicants and m free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.

Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.

Input
The first input line has three integers n, m, and k: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains n integers a1,a2,…,an: the desired apartment size of each applicant. If the desired size of an applicant is x, he or she will accept any apartment whose size is between x−k and x+k.

The last line contains m integers b1,b2,…,bm: the size of each apartment.

Output
Print one integer: the number of applicants who will get an apartment.

Constraints
1 ≤ n, m ≤ $2 \times 10^5$
0 ≤ k ≤ $10^9$
1 ≤ $a_i, b_i$ ≤ $10^9$
Time limit : 1.00s
Memory limit : 512MB

Example

Input :
4 3 5
60 45 80 60
30 60 75

Output :
2

Solution

What is the optimal way to match applicants with appropriate housing? To answer this question, one must make an observation. If possible, the smallest apartment should be given to the applicant who needs less space. This is true because if we give it to another applicant, we may lose the opportunity to give housing to the applicant who needs less space.

We can use this intuition to build a greedy solution. First, we sort both applicants and the apartments sizes in ascending order.

Let us define $i$ and $j$ as variables iterating through the applicants and the apartments respectively, both starting with the first element of the sorted arrays.

The next step is to try and match the $i-th$ applicant with the $j-th$ apartment. There are 3 possible scenarios :

1 : The $i-th$ applicant preferable size is contained in the interval $[x-k,\: x+k]$ where $x$ is the $j-th$ apartment size. If this is the case, we just found a match and increment $i, \: j$ and the answer by 1.

2 : The $i-th$ applicant preferable size is less than $x-k$. This means the apartment is too big for this applicant, hence we increment $i$ by 1. We repeat this until we find a matching applicant.

3 : The $i-th$ applicant preferable size is greater than $x+k$. This means that the apartment is too small and we need to find a new one (note that any applicant further up the list will also not match this apartment). If this is the case, we increment $j$ by 1 and repeat this until the apartment matches the $i-th$ applicant.

We repeat this process for all $N$ applicants and at the end we get our answer.

The following image shows the answer for the sample input.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, m, k, index = 0, answer = 0;
    cin >> n >> m >> k;
    vector<long long> clients(n);
    vector<long long> apartments(m);
    for (int i = 0; i < n; i++) {
        cin >> clients[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> apartments[i];
    }
    sort(clients.begin(), clients.end());
    sort(apartments.begin(), apartments.end());
    for (int i = 0; i < n; i++) {
        while (index < m) {
            if (apartments[index] + k < clients[i]) {
                index++;
            } else if (apartments[index] - k > clients[i]) {
                break;
            } else {
                index++, answer++;
                break;
            }
        }
    }
    cout << answer << endl;
}

Since we are sorting two lists of size $N$ and $M$, the time complexity of this solution is : $$ O(max(N, \:M) \times log(max(N, \: M))) $$ and a space complexity of : $$O(max(N, \: M))$$