Apartments

Solución 1

Explicación

Podemos usar un enfoque voraz para resolver este problema. Primero ordenamos a los solicitantes y los departamentos. Mantenemos dos punteros $i$ y $j$ (inicializados en 0), que llevan el índice actual del solicitante y del departamento que estamos mirando, respectivamente. Luego, mientras queden solicitantes y departamentos por revisar, comprobamos repetidamente lo siguiente:

Si $|\texttt{applicants}[i] - \texttt{apartments}[j]| \leq k$ , hemos encontrado un departamento adecuado para el solicitante actual. Así, incrementamos $i$ , $j$ y nuestra respuesta.
En caso contrario, $\texttt{apartments}[j]$ es o demasiado grande o demasiado pequeño para $\texttt{applicants}[i]$ . Podemos incrementar $i$ o $j$ según corresponda.

Implementación

Complejidad temporal: $\mathcal{O}(n\log(n)+m\log(m))$

C++JavaPython


#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
	int n, m, k;
	cin >> n >> m >> k;
 
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	vector<int> b(m);
	for (int i = 0; i < m; i++) cin >> b[i];
 
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
 
	int i = 0;
	int j = 0;
	int ans = 0;
	while (i < n && j < m) {
		// Found a suitable apartment for the applicant
		if (abs(a[i] - b[j]) <= k) {
			i++;
			j++;
			ans++;
		} 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 << endl;
}


import java.io.*;
import java.util.*;
 
public class Apartments {
	public static void main(String[] args) throws java.lang.Exception {
		BufferedReader fr = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
 
		String[] t = fr.readLine().split(" ");
		int n = Integer.parseInt(t[0]);
		int m = Integer.parseInt(t[1]);
		long k = Integer.parseInt(t[2]);
 
		List<Integer> applicants = new ArrayList<>();
		List<Integer> apartments = new ArrayList<>();
 
		for (String ele : fr.readLine().split(" ")) {
			applicants.add(Integer.parseInt(ele));
		}
 
		for (String ele : fr.readLine().split(" ")) {
			apartments.add(Integer.parseInt(ele));
		}
 
		Collections.sort(applicants);
		Collections.sort(apartments);
 
		int p1 = 0;
		int p2 = 0;
 
		int ans = 0;
		while (p1 < n && p2 < m) {
			// Found a suitable apartment for the applicant
			if (Math.abs(applicants.get(p1) - apartments.get(p2)) <= k) {
				p1++;
				p2++;
				ans++;
				continue;
			}
 
			// If the desired apartment size is too small,
			// skip that applicant and move to the next person
			if (applicants.get(p1) < apartments.get(p2)) p1++;
 
			// If the desired apartment size of the applicant is too big,
			// move the apartment pointer to the right to find a bigger one
			else p2++;
		}
		out.println(ans);
		out.close();
	}
}


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:
	applicant = applicants[i]
	apartment = apartments[j]
 
	if apartment < applicant - tolerance:
		# If the desired apartment size of the applicant is too big,
		# move the apartment pointer to the right to find a bigger one
		j += 1
	elif apartment > applicant + tolerance:
		# If the desired apartment size is too small,
		# skip that applicant and move to the next person
		i += 1
	else:
		# Found a suitable apartment for the applicant
		ans += 1
		i += 1
		j += 1
 
print(ans)

Solución 2

Explicación

Podemos usar el std::multiset de C++ para hallar un departamento que esté en el rango del tamaño deseado de un solicitante.

Con lower bound, podemos hallar el departamento más pequeño que el solicitante puede tolerar.
Si no existe ninguno, no hacemos nada.
En caso contrario, lo quitamos del multiconjunto y sumamos uno a nuestra respuesta. Quitarlo asegura que otro solicitante no pueda tomarlo.

Ordenar a los solicitantes por $a_i$ hace que los tamaños de departamento deseados de cada solicitante queden ordenados de forma creciente. Esto está integrado en el multiconjunto.

Aparte de esto, el espíritu del algoritmo voraz es el mismo que en la solución anterior.

Implementación

Complejidad temporal: $\mathcal{O}((n + m)\log(n)+m\log(m))$

C++


#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++) {
		int temp;
		cin >> temp;
		desired.insert(temp);
	}
 
	vector<int> apartments(m);
	for (int i = 0; i < m; i++) { cin >> apartments[i]; }
	sort(apartments.begin(), apartments.end());
 
	long long res = 0;
	for (int e : apartments) {
		// find an apartment in the range
		auto lower = desired.lower_bound(e - k);
 
		if (lower != desired.end() && *lower <= e + k) {
			res++;
			desired.erase(lower);
		}
	}
 
	cout << res << endl;
}