Question: 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 $a_1$, $a_2$, $\ldots$, $a_n$: 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 $b_1, b_2, \ldots, b_m$: the size of each apartment.
-
Output: Print one integer: the number of applicants who will get an apartment.
Input:
4 3 5
60 45 80 60
30 60 75
Output:
2
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5;
/*
* Variables used for the current problem
* n: number of applicants
* m: number of apartments
* k: max diff between desired and actual size
* a and b: arrays for applicants and apartments respectively
*/
int n, m, k, a[MAX_N], b[MAX_N], ans;
void solve() {
cin >> n >> m >> k;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
sort(a, a + n);
sort(b, b + m);
int i = 0, j = 0;
while (i < n && j < m) {
// Found a suitable apartment for the applicant
if (abs(a[i] - b[j]) <= k) {
++i;
++j;
++a;
} else {
// If the desired apartment size of the applicant is too big,
// move the apartment pointer to the right to find a bigger one
if (a[i] - b[j] > k) {
++j;
}
// If the desired apartment size is too small,
// skip that applicant and move to the next person
else {
++i;
}
}
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}