# Apartments Problem

I first sorted both the applicant and apartment arrays. For applicant x, I want to select the least apartment that is within the range [x-k, x+k]. I take the smallest apartment i because if I choose j > i, there will be at most the same number of ways to give apartments to the remaining applicants. Since applicant y > x has y-k > x-k, j could overlap with the range [y-x, y+k] and limit the possibilities for applicant y. So the smallest apartment within the range of x is optimal.

I implement this using two pointers, as follows.

``````int main()
{
int n, m, k;
cin >> n >> m >> k;
vi a(n), b(m);
F0R(i, n) cin >> a[i];
F0R(i, m) cin >> b[i];
sort(all(a)); //applicants
sort(all(b)); //apartments
int count = 0, j = 0;
trav(i, a) {
// starting from j, what is the first apartment that works?
while (j < m && b[j] < i-k)
j++;
if (j == m) break;
if (j <= i+k) {
count++;
j++; // apartment is sold, look for a new one
}
}
cout << count << endl;
}
``````

This gives a wrong answer on many test cases.

Since I am weak at greedy algorithms, I want to be able to think of greedy methods myself. Please do not reveal the approach to this problem, but please explain why my idea is wrong and how I might start over. To be clear, I would appreciate a nudge in the right direction, not a full thought process.
Thanks!

Your idea is correct but this line should be
` if(b[j] <= i+k)`

Thank you! What a silly mistake. I learned that I need to be more careful and write "index j and apartment b[j]" if necessary. While debugging, I will also look over my code carefully to spot errors such as replacing an index with the array value of that index. Thanks for helping me with this.