CODEWITHSUNDEEP
algorithm
Avinash
Avinash

Reputation: 191

Minimum Distance

There is a set of 9 students and 3 schools Every school can be alloted at max 3 students .Every school and student has its coordinates .Now we have to allot student in such a way that the sum of distance from all the student to the school should be minimum.

I was asked this question in an interview.Can anyone suggest an algorithm for this?

Initially I tried greedy approach but that does not work.Then I tried applying a dynamic programming approach but could not come up with an optimal sub-structure.

Upvotes: 3

Views: 223

Answers (2)

sampson-chen
sampson-chen

Reputation: 47367

How about exhaustive search since the problem size is small enough?

  • First school chooses 3 students out of 9 to start.
  • Second school chooses 3 students out of 6 remaining.
  • Last school gets stuck with the 3 students remaining.

So (9 choose 3) * (6 choose 3) = 1680

Upvotes: 1

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

Every school has 3 places, all 3 schools have 9 places. And you should find the best match between 9 places and 9 students.

This assignment problem may be solved with Hungarian algorithm.

Upvotes: 4

Related Questions