I'm trying to solve the following problem: https://cses.fi/problemset/task/1084/

My first idea to solve this was to sort the applicants and apartments in increasing order. Then, I iterate through all the applicants and for each one, pair it up with the smallest apartment that would satisfy them (if it exists). This greedy strategy managed to correctly answer every test case, but I'm not sure why (because it seems to me that sometimes, it may be better to let another applicant take the apartment we are considering in order to open up more apartments for the rest of the applicants).

Can somebody help prove why this greedy strategy is correct for this problem?

  • 4
    $\begingroup$ Please do include the problem description in the body of the question. Otherwise, when the link is eventually broken, your question will be utterly useless. $\endgroup$ Sep 25 '21 at 13:02

Let the applicants demands in the increasing order is: $d_1, \dotsc,d_{n}$.

Let the apartments sizes in the increasing order is: $s_1, \dotsc,s_{m}$.

Try to prove the following claim:

Claim: Let $d_i \leq d_j$ and $s_x \leq s_y$. If $d_i$ can be assigned to $s_y$, and $d_j$ can be assigned to $s_x$. Then, it is possible to assign $d_i$ to $s_x$, and $d_j$ to $s_y$.

For proof, try to take cases like $d_i \leq s_x$ or $d_i>s_x$. Using it you can show that $d_i$ can be assigned to $s_x$. Using similar cases, you can further show that $d_j$ can be assigned to $s_y$.

I leave the rest of the details to you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.