I was given the following algorithms problem:

Suppose you have $n$ cities. Each city $c_i$ has population $p_i$. You want to construct $m \geq n$ schools, where each school can only serve students of its city, and fulfill two objectives:

  1. Every city must have at least $1$ school.

  2. You want to allocate schools to cities such that the maximum number of people served by any one school is minimized.

I came up with the following naive algorithm to allocate schools to cities, but found that it is too slow in practice.

  1. Assign one school to every city.
  2. Keep a list of triples, where one triple $t_i$ represents the following information for city $c_i$: (number of schools, population, population divided by number of schools)
  3. While the number of schools left to assign is not zero:
    1. Find the triple with the maximal population divided by number of schools.
    2. Assign one more school to that city.

My insight here was that minimizing the maximal number of students in any school is exactly the same as minimizing the average number of students per school in any city.

Regardless, the algorithm I lined out above is far too slow in practice, because finding the triple with that maximum is a linear-time operation in the number of cities. (Additionally, I assume that some clever optimizations could let us assign multiple schools to cities at once -- proceeding one-by-one is likely also slower than necessary.) The problem statement leads me to believe that maybe I could use integer programming or dynamic programming, but I'm not sure. What is an efficient algorithm to solve this problem? Are there analogous problems?

  • $\begingroup$ Where did you encounter this problem? I encourage you to acknowledge the source of the problem. $\endgroup$ – D.W. Feb 21 '17 at 7:19
  • $\begingroup$ @D.W. I encountered this problem in a quiz. I have changed some of the details, but the underlying challenge is the same. $\endgroup$ – Newb Feb 21 '17 at 7:23
  • $\begingroup$ Can a single school serve two cities (e.g., serve 100 students from city 1 and 200 students from city 2)? $\endgroup$ – D.W. Feb 21 '17 at 17:56
  • $\begingroup$ @D.W. A single school can only serve students from its city. Sorry about the omission of that detail; I've edited the question appropriately. $\endgroup$ – Newb Feb 21 '17 at 18:44

Hint: Binary search is often a helpful strategy.

Another hint:

Suppose you want to find out whether it's possible to find a way to allocate schools to cities, so that every school serves at most $s$ students. Could you figure out the answer to that question, if $s,m,n$ and the $p_i$ were given as input? I bet you could. You should be able to solve that one, in $O(n)$ time. Now you should know what to do....

  • $\begingroup$ But you don't know what s is $\endgroup$ – paparazzo Feb 21 '17 at 21:39
  • $\begingroup$ @Paparazzi, Correct! You might notice I gave two hints -- you'll need to combine both of them to get a working solution. (I purposely didn't provide a complete solution, since the problem looks like an exercise, and I'd like them to have the chance at finding a solution themselves.) $\endgroup$ – D.W. Feb 21 '17 at 21:40
  • $\begingroup$ @D.W. Thanks for a great solution. Using the two hints in conjunction readily yielded the answer. :-) $\endgroup$ – Newb Feb 25 '17 at 6:15
  • allocate 1 school to each of the cities and calculate average school size
    this first pass will just be city size at it has 1 school
  • sort on average school size for each city
    with highest average first
    I think $\mathcal{O}(n*log(n))$
  • add 1 school to top for the sorted cities above and take new average school size
    average is city size / number of schools
  • using binary to re-sort that one city by average school size
  • you must do the above two steps m-n times so

Sum and get $\mathcal{O}(m*log(n))$

Thinking out loud best possible case is each school has the exact same number of students so could take the total number of students and divided by m. Assign enough schools to each city to get to that number and round down (every school is over the optimal number). Any city with no school gets 1 school. Hopefully you have some schools left over. Then use the algorithm above starting at step (bullet) 2. I suspect there are edge cases this does not cover. Round down from 301 to 300 is not going to have the same effect as round down from 3 to 2.

If you do not have schools left over then then I think you could take schools in order from lowest average.

  • $\begingroup$ What does "sort with highest average first" mean? What are you sorting, and in what order? I can't make sense of this answer. $\endgroup$ – D.W. Feb 21 '17 at 21:26
  • $\begingroup$ @D.W. Sort on average school size $\endgroup$ – paparazzo Feb 21 '17 at 21:28
  • $\begingroup$ That makes no sense to me. What does "average school size" mean? What average are you talking about? Average of what? There's one school per city. The only average I can think of is the average number of students per school. But that's a single number (not one number per school) so it's not something you can use to sort the schools or to sort the cities. So what are you trying to say? What are you trying to sort? And what key value are you using to sort on? $\endgroup$ – D.W. Feb 21 '17 at 21:29
  • $\begingroup$ @D.W. Average school size is city population divided by number of schools. Yes it starts with one school per city but then you add a school the basically the city that needs it the most. $\endgroup$ – paparazzo Feb 21 '17 at 21:32
  • $\begingroup$ OK, cool. I encourage you to edit your answer to define all concepts that you use before first using that term, so that we can understand what you're trying to do. Don't force us to guess what you might have in mind. Next questions: What does "add 1 school to top" mean? What does "using binary to re-sort that one city" mean? $\endgroup$ – D.W. Feb 21 '17 at 21:35

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.