CSES 2. Apartments (1084)

출처: https://cses.fi/problemset/task/1084

---

문제 설명

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.

입력 

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 mm integers b_1,b_2,…,b_m: the size of each apartment.

출력

Print one integer: the number of applicants who will get an apartment.

입력 예

4 3 5
60 45 80 60
30 60 75

출력 예

2

제약조건

• 1 <= n,m <= 2x10^5
• 0 <= k <= 10^9 
• 1 <= a_i, b_i <= 10^9

---

문제 풀이

아파트 크기와 원하는 크기를 입렵 받아서 작은 순서로 정렬한다.

원하는 크기와 감당할 수 있는 크기차이와 주어진 아파트의 크기를 비교해서, 가능한 방들을 출력한다.

프로그램 내용

#define MAX_N 2*100000
#define MAX_M 2*100000
#define MAX_K 1000000000
#define MAX_A 1000000000
#define MAX_B 1000000000

int main()
{
    int nApplicant, nApart, maxDiff;
    cin >> nApplicant >> nApart >> maxDiff;

    long desired[nApplicant];
    long aptSize[nApart];

    for (int idx=0; idx<nApplicant; ++idx)
        cin >> desired[idx];

    for (int idx=0; idx<nApart ; ++idx)
        cin >> aptSize[idx];

    sort(desired, desired+nApplicant);
    sort(aptSize, aptSize+nApart);

    int idx=0, id=0;
    int room_count=0;

    while(idx < nApplicant && id < nApart)
        if (desired[idx]+maxDiff < aptSize[id]) 
        	idx++;
        else if (desired[idx]-maxDiff > aptSize[id]) 
        	id++;
        else 
        	idx++; 
            id++; 
            room_count++;

	cout << room_count << endl;

 

Sorting and Searching ( link )