There are n applicants and m free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.
Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.
Input
The first input line has three integers n, m, and k: the number of applicants, the number of apartments, and the maximum allowed difference.
The next line contains n integers a_1, a_2, …, a_n: the desired apartment size of each applicant. If the desired size of an applicant is x, he or she will accept any apartment whose size is between x-k and x+k.
The last line contains m integers b_1, b_2, …, b_m: the size of each apartment.
Output
Print one integer: the number of applicants who will get an apartment.
Constraints
1 less than or equal to n, m less than or equal to 2 * 10^5
0 less than or equal to kl ess than or equal to 10^9
1 less than or equal to a_i, b_i less than or equal to 10^9
Example
Input:
4 3 5
60 45 80 60
30 60 75
Output:
2
My attempt so far:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int m;
int n;
int k;
cin >> n >> m >> k;
multiset<int> desired;
multiset<int> actual;
int input;
for (int i = 0; i < n; i++)
{
cin >> input;
desired.insert(input);
}
for (int i = 0; i < m; i++)
{
cin >> input;
actual.insert(input);
}
}
So far, I’ve taken the input of n, m, and k. I then took the second line of input which is the desired apartment sizes and stored them inside a multiset named desired. I then did the same with the actual apartment sizes and stored them inside a multiset named actual. I don’t know what to do from here :(. Can I have a hint on solving it please?
Jekyll is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.