1

We are going to hold a meeting where everybody will speak in clockwise direction around a table. There are n people with n spots. Each person has a position preference (e.g. some want to go first, some last, etc). Everyone is seated randomly and cannot move from their position. How shall we compute the best starting position on the table to satisfy the most people?

I have an O(n^2) solution: See how many people would be satisfied having assumed each of the positions 1..n as start positions; then return the position that gave the maximum value.

d'alar'cop
  • 121
  • 5
  • NB I will give a generous bounty ASAP if someone solves this – d'alar'cop Mar 13 '14 at 09:08
  • That's not the way it works. You assign the bounty first, *then* maybe someone will be attracted to try the problem at all. – Kilian Foth Mar 13 '14 at 09:12
  • Yes, I know - but I need to wait 2 days before I can do that – d'alar'cop Mar 13 '14 at 09:12
  • 1
    Are people only satisfied if they speak exactly at the position they wanted to, or would they also be content if they speak *near* their position (e.g. if someone wants to go first, but has to go second, that would be suboptimal but still better than going last?) – amon Mar 13 '14 at 09:13
  • @amon They are "satisfied" if and only if they are given their exact preference. 1 space away might as well be n/2 away :) – d'alar'cop Mar 13 '14 at 09:14

2 Answers2

4

If each person knows exactly what order he wants to go in and the seating order is constant, then each person knows what starting position he wants the speaking to start at. This way, you can calculate how many people want speaking start at specific points, which is O(n) in complexity if you the preferred position as index into array.

Euphoric
  • 36,735
  • 6
  • 78
  • 110
  • +1 Thanks! I know you were first... and the answers are equivalent in concept... but amon gave a more formal response with some code. – d'alar'cop Mar 13 '14 at 09:31
  • +1 This somehow explained it to me better than the answer with the code – dj18 Mar 13 '14 at 19:14
4

A fairly simple O(n) algorithm exists:

Let pos be an array so that if the person at seat i wants to speak as n-th, we have an entry pos[i] = n. Where the numbering of the seats starts is irrelevant. Both i and n start counting with zero.

The difference i - pos[i] is the seat where the round would have to start for the person at seat i to be satisfied. We count the satisfied persons per start position in a satisfied array. We can then find the maximum of that array, the index of the maximum is the seat where the round should start for maximum satisfaction.

Java example:

int findBestStart(int[] pos) {
    // ask each seat where they'd like to start
    int[] satisfied = new int[pos.length];
    for (int i = 0; i < pos.length; i++) {
        int start = i - pos[i]
        if (start < 0) start += pos.length;
        satisfied[start]++;
    }

    // find where most would like to start
    int bestSeat = -1;
    int bestSatisfied = -1;
    for (int i = 0; i < satisfied.length; i++) {
        if (satisfied[i] > bestSatisfied) {
            bestSeat = i;
            bestSatisfied = satisfied[i];
        }
    }

    return bestSeat;
}
amon
  • 132,749
  • 27
  • 279
  • 375