Consider the following scenario. Due to large-scale flooding in a re- gion, paramedics have identified a set of n injured people distributed across the region who need to be rushed to hospitals. There are k hos- pitals in the region, and each of the n people needs to be brought to a hospital that is within a half-hour’s driving time of their current location (so different people will have different options for hospitals, depending on where they are right now).

At the same time, one doesn't want to overload any one of the hospitals by sending too many patients its way. The paramedics are in touch by cell phone, and they want to collectively work out whether they can choose a hospital for each of the injured people in such a way that the load on the hospitals is balanced: Each hospital receives at most [n/k] people.

Give a polynomial-time algorithm that takes the given information about the people's locations and determines whether this is possible.