CSES - Apartments

Authors: Nathan Gong, Danh Ta Chi Thanh


Unofficial Editorial (C++)

We can use a greedy approach to solve this problem. First, sort the applicants and apartments. We can keep two pointers ii and jj (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 applicants[i]apartments[j]k|\texttt{applicants}[i] - \texttt{apartments}[j]| \leq k, we have found a suitable apartment for the current applicant. Thus, we increment ii, jj, and our answer.
  • Otherwise, apartments[j]\texttt{apartments}[j] is either too big or too small for applicants[i]\texttt{applicants}[i]. We can increment ii or jj accordingly.

Implementation

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

C++

#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

Java

Warning!

Java will TLE on test case #17.

import java.io.*;
import java.util.*;
public class Apartments {
public static void main(String[] args) {
Kattio io = new Kattio();
int n = io.nextInt(); // number of applicants
int m = io.nextInt(); // number of apartments
int k = io.nextInt(); // max diff between desired and actual size

Python

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:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!