DSA sheet / Sorting and searching
Apartments
Do these first: Distinct Numbers
The problem in brief
There are n applicants, each with a desired apartment size, and m apartments with given sizes (n and m up to 200 000). Someone accepts an apartment if its size is within k of what they want. Each apartment goes to at most one applicant. Print the largest possible number of applicants who get an apartment.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1084.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Doing this over the raw, unordered lists forces you to compare everyone with everyone. What does sorting both lists buy you?
-
After sorting, look at the smallest remaining applicant and the smallest remaining apartment. There are only three possibilities for how they relate. What should you do in each?
-
If the apartment is too small for even the smallest applicant, can any later applicant use it? Can that apartment ever be useful again?
-
If the pair is acceptable, is there any reason not to match them immediately?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
A matching problem with a “closeness” rule on one number line is usually greedy after sorting. The brute force (try all assignments, or run general bipartite matching) is far too heavy here, so ask what structure the numbers give you: everything lives on a line, and acceptability is an interval of width 2k around each desire.
Reason about the extremes. The smallest apartment is either too small for the smallest applicant (then it is too small for everyone larger too, so discard it), or too large for them (then no apartment can ever be closer to them from below, so discard the applicant), or a fit (then match them; the alternative of saving that applicant for a bigger apartment cannot be better, because a bigger apartment can serve later applicants at least as well). Each comparison retires at least one person or apartment, which is the pattern of two pointers.
The habit: sort, then decide by comparing the two smallest remaining items and argue that the item you drop can never be part of a better solution (an exchange argument).
Intuition
Line up applicants by wish size and apartments by size, both from small to large, and walk two fingers along. Whenever the fingers point at a compatible pair, tie them together and move both. Otherwise the one that is left behind on the number line is hopeless, so move its finger.
Approach
- Sort the desired sizes a and the apartment sizes b.
- Let i = 0, j = 0, matches = 0.
- While i < n and j < m: if |a[i] - b[j]| <= k, count a match and advance both; else if a[i] < b[j] - k (apartment too big for this applicant) advance i; otherwise (apartment too small) advance j.
- Print matches.
Edge cases: k = 0 (exact match only), every apartment too small or too large, n or m equal to 1. Sizes up to 10^9 and k up to 10^9, so use 64-bit for the differences (in C++ a[i] - b[j] with ints stays within range, but b[j] - k style expressions may not, so compare via the absolute difference).
Complexity
O(n log n + m log m) for sorting, then O(n + m) for the sweep. O(n + m) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
long long k;
cin >> n >> m >> k;
vector<long long> a(n), b(m);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int i = 0, j = 0, matches = 0;
while (i < n && j < m) {
if (llabs(a[i] - b[j]) <= k) {
matches++;
i++;
j++;
} else if (a[i] < b[j]) {
i++; // this apartment is too big for the smallest remaining applicant
} else {
j++; // this apartment is too small for everyone left
}
}
cout << matches << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, m, k = int(data[0]), int(data[1]), int(data[2])
a = sorted(map(int, data[3:3 + n]))
b = sorted(map(int, data[3 + n:3 + n + m]))
i = j = matches = 0
while i < n and j < m:
if abs(a[i] - b[j]) <= k:
matches += 1
i += 1
j += 1
elif a[i] < b[j]:
i += 1 # apartment too big for the smallest remaining applicant
else:
j += 1 # apartment too small for everyone left
print(matches)
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int m = (int) st.nval;
st.nextToken();
long k = (long) st.nval;
long[] a = new long[n];
long[] b = new long[m];
for (int i = 0; i < n; i++) {
st.nextToken();
a[i] = (long) st.nval;
}
for (int i = 0; i < m; i++) {
st.nextToken();
b[i] = (long) st.nval;
}
Arrays.sort(a);
Arrays.sort(b);
int i = 0, j = 0, matches = 0;
while (i < n && j < m) {
if (Math.abs(a[i] - b[j]) <= k) {
matches++;
i++;
j++;
} else if (a[i] < b[j]) {
i++;
} else {
j++;
}
}
System.out.println(matches);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const [n, m, k] = data;
// Typed-array sort is numeric and fast; no comparator needed.
const a = Float64Array.from(data.slice(3, 3 + n)).sort();
const b = Float64Array.from(data.slice(3 + n, 3 + n + m)).sort();
let i = 0;
let j = 0;
let matches = 0;
while (i < n && j < m) {
if (Math.abs(a[i] - b[j]) <= k) {
matches++;
i++;
j++;
} else if (a[i] < b[j]) {
i++;
} else {
j++;
}
}
console.log(matches);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).