Apartments

Abridged problem statement

Given two multisets $A$ and $B$, and a number $k$, find the size of a maximum matching given that two elements $a \in A, b \in B$ can be matched iff $|a-b| \le k$.

That is, form as many pairs $(a,b)$ with $a \in A, b \in B$ as possible, using every element at most once.

You should take a minute to think about why the original problem statement is equivalent to this abridged version.

Solution

Again, with most greedy problems, there’s really no good way to begin. However, there are things we can try. Allow me to introduce you to another tool you should add to your toolkit: the extremal principle.

The idea behind this problem-solving technique is simple–a complicated problem may be simpler to think about if we consider ’extremal’ cases—that is, cases involving the minimum and maximum elements.

Let’s think about the minimum element across both $A$ and $B$, call this $m$, and let’s assume that $m \in A$. Maybe our two sets look something like this:

Here, the blue circles denote elements in $A$ (the leftmost blue element is $m$), and the orange circles denote elements in $B$.

In this case, we cannot match $m$ with any element in $B$. Thus, it seems reasonable to assume that the answer will remain unchanged if we remove $m$ from $A$?

But what if the distance between $m_a:=\min\{A\}$ and $m_b:=\min\{B\}$ was $\le k$?

We could then match $m_a$ with $m_b$, but should we?

An optimal matching?

Suppose we already have an optimal matching. If it is possible to modify this matching so that it:

• Remains valid
• Now includes $(m_a, m_b)$
• Has the same (or better) cardinality as before

then we will have successfully proven that there exists an optimal matching containing $(m_a, m_b)$. It remains to be seen whether or not this is possible.

To begin with, consider this extremely simple case:

We can simply match $m_a$ with $m_b$ without making any other changes. Next, consider this case:

We can include $(m_a, m_b)$ by removing the existing matching $m_b$ is a part of and matching it with $m_a$ instead. The number of matchings remains unchanged.

The most interesting case is when both $m_a$ and $m_b$ are matched:

I claim that the following replacement is possible:

The proof is straightforward. Let the two matched pairs be $(m_a,B_1)$ and $(A_1,m_b)$.

We already know that $(m_a,m_b)$ is valid because $|m_a-m_b|\le k$. We only need to prove that $(A_1,B_1)$ is also valid.

Since $m_a$ and $m_b$ are the minimum elements of their respective sets,

Now consider the relative order of $A_1$ and $B_1$:

• If $B_1<A_1$ (this is what’s depicted in the above diagram), then

because $(A_1,m_b)$ was a valid pair.

• If $A_1\le B_1$, then

because $(m_a,B_1)$ was a valid pair.

Therefore, $|A_1-B_1|\le k$ in either case. Thus, we can replace the pairs $(m_a,B_1)$ and $(A_1,m_b)$ with $(m_a,m_b)$ and $(A_1,B_1)$ without changing the matching’s cardinality.

If this is your first time solving this problem, keep in mind that this is a hard and novel idea, and you may benefit from a re-read. Anyway, with all that work, we’ve concluded that matching $(m_a, m_b)$ (when we can) is always optimal. Then, we set

and

When we can’t, it’s safe to discard the smaller of the two.

Implementation

A simple two-pointer approach suffices.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int n, m, k;
  cin >> n >> m >> k;
 
  vector<int> a(n), b(m);
  for (int &i : a) {
    cin >> i;
  }
  for (int &i : b) {
    cin >> i;
  }
 
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
 
  int ans = 0;
 
  int i = 0, j = 0;
  while (i < int(a.size()) && j < int(b.size())) {
    if (abs(a[i] - b[j]) > k) {
      if (a[i] < b[j]) {
        i++;
      } else {
        j++;
      }
      continue;
    }
    ans++;
    i++, j++;
  }
 
  cout << ans << '\n';
}