CSES - Apartments
Authors: Nathan Gong, Danh Ta Chi Thanh
We can use a greedy approach to solve this problem. First, sort the applicants and apartments. We can keep two pointers and (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 , we have found a suitable apartment for the current applicant. Thus, we increment , , and our answer.
- Otherwise, is either too big or too small for . We can increment or accordingly.
Implementation
Time Complexity:
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 applicantsint m = io.nextInt(); // number of apartmentsint 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 pointerj = 0 # Apartment pointerans = 0while 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!