Unofficial Editorial (C++)

We can use a greedy approach to solve this problem. First, sort the applicants and apartments. We can keep two pointers $i$ and $j$ (initialized to 0), which keep track of the current index of the applicant and apartment we are looking at respectively. Then, while there are more applicants and apartments to look through, we repeatedly run the following check:

• If $|\texttt{applicants}[i] - \texttt{apartments}[j]| \leq k$, we have found a suitable apartment for the current applicant. Thus, we increment $i$, $j$, and our answer.
• Otherwise, $\texttt{apartments}[j]$ is either too big or too small for $\texttt{applicants}[i]$. We can increment $i$ or $j$ accordingly.

Implementation

Time Complexity: $\mathcal{O}(n\log(n)+m\log(m))$

Copy
n, m, tolerance = map(int, input().split())
applicants = list(map(int, input().split()))
apartments = list(map(int, input().split()))
applicants.sort()
apartments.sort()

i = 0  # Applicant pointer
j = 0  # Apartment pointer
ans = 0
while i < n and j < m: