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?