Editorial for JDCC '16 Contest 2 P3 - Shoe Rental


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: aurpine

This is a greedy solution. We will prioritize smaller shoe sizes so that we save large shoe sizes for people who may require them.

To do this, we will sort the required sizes in ascending order. Then we process from the smallest one and see if there is a shoe available with size m - 1, then m, then m + 1.

Alternatively, you can use radix sort to get an array of how many people need each shoe size and do the similar process of assigning shoes.

Time Complexity: \mathcal{O}(N \log N) or \mathcal{O}(N) with radix sort.


Comments

There are no comments at the moment.