Unofficial Editorial (C++)

Solution 1

Explanation

We can use a greedy approach to solve this problem. First, we sort the applicants and apartments. We 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 check the following:

• 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:

Solution 2

Explanation

We can use C++'s std::multiset to find an apartment that is in the range of an applicant's desired size.

• Using lower bound, we can find the smallest apartment the applicant can tolerate.
• If none exists, we do nothing.
• Otherwise, we remove it from the multiset and add one to our answer. Removing it makes sure another applicant cannot take it.

Sorting the applicants by $a_i$ results in the desired apartment sizes for each applicant being sorted in increasing value. This is built into the multiset.

Besides this, the spirit of the greedy algorithm is the same as in the previous solution.

Implementation

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

Copy
#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, m, k;
	cin >> n >> m >> k;

	multiset<int> desired;
	for (int i = 0; i < n; i++) {